import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param proot TreeNode类
* @param k int整型
* @return int整型
*/
// 辅助函数:计算树的节点数
public int count (TreeNode proot) {
// write code here
if (proot == null)
return 0;
return 1+count(proot.left)+count(proot.right);
}
// 判断左右子树的个数,然后决定传到左子树还是右子树中
// 时间复杂度:O(n^2)空间复杂度:O(n)
public int KthNode (TreeNode proot, int k) {
// write code here
if (proot == null || k < 1 || count(proot) < k)
return -1;
if (count(proot.left) == k-1)
return proot.val;
else if (count(proot.left) > k-1)
return KthNode(proot.left, k);
else
return KthNode(proot.right, k-count(proot.left)-1);
}
}