二叉搜索树的第k个结点

发表于 | 分类于 ，

求 二叉搜索树的第k个结点

给定一颗二叉搜索树，请找出其中的第k大的结点。

例如:

     5
   /  \
  3    7
 / \  / \
2  4 6   8

中，按结点数值大小顺序第三个结点的值为4。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static TreeNode KthNode(TreeNode pRoot, int k) {
    if (pRoot == null || k < 1) {
        return null;
    }
    Stack<TreeNode> stack = new Stack<>();
    int count = 0;
    TreeNode KthNode = null;
    while (pRoot != null || !stack.isEmpty()) {
        while (pRoot != null) {
            stack.push(pRoot);
            pRoot = pRoot.left;
        }
        TreeNode node = stack.pop();
        count++;
        if(count == k){
            KthNode = node;
        }        
        pRoot = node.right;         
    }
    return KthNode;

}