leetcode:230.ツリー内のK番目に小さい要素(javaツリー)を検索
1308 ワード
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);
}
}