《剑指offer第二版》面试题54：二叉搜索树的第K大节点（java）

题目描述

• 给定一棵二叉搜索树，请找出其第K大的节点。

解题思路

1. 二叉搜索树的中序遍历结果是递增排序的
2. 只需中序遍历第K个节点即可。

代码

class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.value = val;
    }
}
int kthNode(TreeNode root, int k){
    if (root == null) {
        return -1;
    }
    return inOrderTravel(root, k);
}

int inOrderTravel(TreeNode node, int k) {
    Stack<TreeNode> stack = new Stack<>();
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        TreeNode tmp = stack.pop();
        //System.out.println(tmp.value);
        k--;
        if (k == 0) {
            return tmp.value;
        }
        node = tmp.right;
    }
    return -1;
}