用中序遍历访问BST

题目链接-来源：力扣（LeetCode）

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

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/
1 4

  2
输出: 4

思路：

由于我们无法提前知道二叉树的节点总数，因此只能通过遍历的方式计数访问其第 k 个节点。
BST 的中序序列能按从小到大的顺序输出节点值，因此我们在中序遍历的基础上，增加一个计数变量 k 作为跳出条件即可。这里展示非递归实现的思路。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int kthLargest(TreeNode root, int k) {
        TreeNode cur = root;
        Stack<TreeNode> s = new Stack<>();
        while (k != 0) {
            while (cur != null) {
                s.push(cur);
                cur = cur.right;
            }
            cur = s.pop();
            if (--k == 0) {
                break;
            }
            cur = cur.left;
        }
        return cur.val;
    }
}