题解 | #二叉搜索树的第k个节点# 【迭代 & 中序遍历】
二叉搜索树的第k个节点
https://www.nowcoder.com/practice/57aa0bab91884a10b5136ca2c087f8ff
1. 方法一：迭代法
2. 方法二：中序遍历
// 方法一：迭代法
public int KthNode1 (TreeNode proot, int k) {
// write code here
if(proot == null || k == 0) return -1;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = proot;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
if(!stack.isEmpty()){
cur = stack.pop();
if(--k == 0){
return cur.val;
}
}
cur = cur.right;
}
return -1;
}
-----------------
// 方法二：中序遍历
List<Integer> list = new ArrayList<>();
public int KthNode (TreeNode proot, int k) {
// write code here
if(proot == null || k == 0) return -1;
inOrder(proot);
return k <= list.size() ? list.get(k-1) : -1;
}
private void inOrder(TreeNode proot){
if(proot == null) return;
inOrder(proot.left);
list.add(proot.val);
inOrder(proot.right);
}