【专题二 二叉树中的深搜】230. 二叉搜索树中第K小的元素

1.题目解析

2.讲解算法原理 

         首先抓住二叉搜索树中序遍历是一个有序序列，第k大的数字，是将遍历的结果找到第k个，这时如果采用全局变量会更加容易，设置两个全局变量count和ret。其中count用来存储是第几个小的数字，而ret则用来存储这个数的数值。

        出口条件是，一旦root为空或者count==0时，返回。

3.编写代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int count;
    public int ret;
    public int kthSmallest(TreeNode root, int k) {
        count=k;
        dfs(root);
        return ret;
       
    }
    public void dfs(TreeNode root){
     if(root==null){
        return;
     }
     dfs(root.left);
     if(count==0){
        return;
     }else{
        count--;
        ret=root.val;
     }
      dfs(root.right);
    }
     
       

}

原文地址：https://blog.csdn.net/2401_83227065/article/details/145247670

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！