lc剑指 Offer 54. 二叉搜索树的第k大节点（反中序遍历）

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

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4

限制：

1 ≤ k ≤ 二叉搜索树元素个数

class Solution {
    public int kthLargest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.addLast(root);
                root = root.right;
            } else {
                root = stack.pollLast();
                if (--k == 0) return root.val;
                root = root.left;
            }
        }
        return -1;
    }
}