用迭代法中序遍历得到升序数组,然后索引得到,此时空间复杂度为O(N2)

但是同样采用中序遍历,不需要得到最后的升序数组,只需要一个变量记录第几个数,等到等于k时,即返回,此时空间复杂度可以提升到O(N)

O(N),O(N)

public class Solution {
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param proot TreeNode类 
 * @param k int整型 
 * @return int整型
 */
public int KthNode (TreeNode proot, int k) {
    // write code here
    //用迭代法中序遍历得到非降序数组,然后索引得到,此时空间复杂度为O(N2)
    //但是同样采用中序遍历,只需要一个变量记录第几个数,等到等于k时,即返回,此时空间复杂度可以提升到O(N)
    if(proot == null) return -1;
    Stack<TreeNode> stack = new Stack<>();
    
    TreeNode cur = proot;
    while(cur != null || !stack.empty()){
        if(cur != null){
            stack.push(cur);
            cur = cur.left;
        }else{
            TreeNode node = stack.pop();
            k --;
            cur = node.right;
            if(k == 0) return node.val;
        }
    }
    return -1;//k > n
}
}

此题当然可以可以采用递归中序

O(N),O(N)

public class Solution {
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param proot TreeNode类 
 * @param k int整型 
 * @return int整型
 */
ArrayList<Integer> nums =  new ArrayList<>();
public int KthNode (TreeNode proot, int k) {
    // write code here
    if(proot == null || k <= 0) return -1;//mark
    
    track(proot);
    if(k > nums.size()) return -1;

    return nums.get(k - 1);
}

public void track(TreeNode root){
    if(root == null) return;
    track(root.left);
    nums.add(root.val);
    track(root.right);
}
}