题目描述
给定一颗二叉搜索树，请找出其中的第k大的结点。
思路
1.中序遍历二叉搜索树
2.递归调用
代码1
Common.TreeNode KthNodeII(Common.TreeNode pRoot, int k) {
if (pRoot == null || k < 0)
return null;
Stack<Common.TreeNode> stack = new Stack<>();
Common.TreeNode node = pRoot;
int count = 0;
while (node != null || !stack.isEmpty()) {
while (node!= null) {
stack.push(node);
node = node.left;
}//左子树为空或已经被访问
if (!stack.isEmpty()) {
node=stack.pop();//访问根节点
count++;
if (count == k)
return node;
node = node.right;//处理右子树
}
}
return null;
}
代码2
Common.TreeNode KthNode(Common.TreeNode pRoot, int k) {
if (pRoot == null || k < 0)
return null;
Common.TreeNode res;
if ((res = KthNode(pRoot.left, k)) != null)//左子树找到，则返回
return res;
count++;//访问过左子树，count+1
if (k == count)//如果相等，说明当前节点就是要找的第k个节点
return pRoot;
res = KthNode(pRoot.right, k);//如果还没找到，查找右子树
if (res != null)
return res;
return null;
}
