用迭代法中序遍历得到升序数组,然后索引得到,此时空间复杂度为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);
}
}