二叉搜索树的第k个结点
给定一棵二叉树，请找出其中的第k大的结点
分析：
二叉搜索树的中序遍历是递增顺序的
public class KthNodeInBST<Key extends Comparable<Key>> {
private class Node {
public Key key;
public Node left, right;
public Node(Key key) {
this.key = key;
}
}
public Node kthNode(Node root, int k) {
if (root == null || k <= 0) {
return null;
}
return kthNodeCore(root, k);
}
private Node kthNodeCore(Node node, int k) {
Node target = null;
if (node.left != null) {
target = kthNodeCore(node.left, k);
}
if (target == null) {
if (k == 1) target = node;
k--;
}
if (target == null && node.right != null) {
target = kthNodeCore(node.right, k);
}
return target;
}
}
