leetcode:230.ツリー内のK番目に小さい要素(javaツリー)を検索


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);
    }
}