给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
中序遍历二叉搜索树 -> 递增排列
TreeNode KthNode(TreeNode pRoot, int k) {
if(pRoot == null || k <= 0)return null;
int index = 1;
Stack<TreeNode> s = new Stack<>();
while(!s.isEmpty() || pRoot != null) {
while(pRoot!=null) {
s.push(pRoot);
pRoot = pRoot.left;
}
pRoot = s.pop();
if(index++ == k)
return pRoot;
pRoot = pRoot.right;
}
return null;
}