leetcode:230. 二叉搜索树中第K小的元素(java树)

末蓝、 2021-09-28 10:42 210阅读 0赞

package LeetCode;
    /*
    给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
    说明：
    你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
    示例 1:
    输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 1
    示例 2:
    输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 3
     */
    public class KthSmallest {
        TreeNode res;
    
        public int kthSmallest(TreeNode root, int k) {
            serch(root, k);
            return res == null ? -1 : res.val;
        }
    
        int serch(TreeNode root, int k) {
            if (root == null) {
                return 0;
            }
            //先向左子树进行遍历到最后（整体计数是县遍历到左子树最后一个然后进行返回开始一个一个计数）
            int c = serch(root.left, k);
            int c2 = 0;
            //如果找到的相应的结果则退出
            if (res != null || k <= c) {
                return c;
                //每一个最后结束都会在此处返回 当前根节点是第k个值
            } else if (k - c == 1) {
                res = root;
                return k;
                //左子树满足不了则进行向当前节点的右子树进行搜索 k=原来的k减去左子树的和根节点的
            } else {
                c2 = serch(root.right, k-c-1);
            }
            //此节点的左子树右子树和根节点
            return c + 1 + c2;
        }
    
        public static void main(String[] args) {
            KthSmallest k=new KthSmallest();
            TreeNode t1=new TreeNode(1);
            TreeNode t2=new TreeNode(2);
            t1.right=t2;
            k.kthSmallest(t1,2);
        }
    }