二叉搜索树的第k个结点

求问大佬，如果使用数组或者集合去遍历存储节点的话，还属于是O(1)的空间复杂度吗？

贼清楚写的！

萌新问一下，为什么选择中序遍历

中序遍历递归写法还得把遍历的节点放入数组明显麻烦，非递归可以直接过程中判断是否到第k个数了。 import java.util.LinkedList; public class Solution { TreeNode KthNode(TreeNode pRoot, int k){ LinkedList<treenode> nodeStack = new LinkedList<treenode>(); TreeNode current = pRoot; int count = 0; while (current != null || !nodeStack.isEmpty()) { while (current != null) { nodeStack.addFirst(current); current = current.left; } if (!nodeStack.isEmpty()) { current = nodeStack.removeFirst(); count ++; if (count == k) { return current; } current = current.right; } } return null; } }</treenode></treenode>

一定优化后的中序遍历递归写法，在in_order(root.right, stack);前加一个if(K>0)判断剪枝，这样中序遍历就不用遍历完整棵树了 import java.util.Stack; public class Solution { int K; TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot==null||k<=0) return null; K=k; Stack<treenode> stack=new Stack<>(); in_order(pRoot, stack); //K还大于0,说明k>节点个数，所以返回null，而不是栈顶结点（最大结点） if(K>0) return null; else return stack.pop(); } void in_order(TreeNode root, Stack<treenode> stack){ //System.out.println("执行1次"); if(root==null) return; //第一个if尽量减少入栈次数，第二个if尽量减少递归次数 in_order(root.left, stack); if(K>0) {stack.push(root); K--;} if(K>0) in_order(root.right, stack); } }</treenode></treenode>