二叉搜索树的第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

然后引出我们的第一种解法，递归，其实就是上面那种遍历方式的变形，我们不需要遍历完这个二叉树，我们只需要遍历到第k大的就好，所以我们要定义一个全局变量count为k（如果要是递归中使用局部变量会随着方法的弹栈而变化，不好控制），每遍历到一个节点我们就减一，直到count等于1，这时遍历到的数字就是最大的，我们此时记录答案终止递归，return方法即可；这种方法罕见的在leetcode上内存和时间都击败了100%的JAVA同学；

 

这种迭代的方式使用了栈结构，主要的思想就是，一个节点的右节点一定比这个节点的左子树乃至父节点都大，所以我们需要利用栈结构迭代找到最右边的节点，当右节点遍历完了之后，再看一下这个右节点有没有左子节点（因为这个右节点的左子节点也比这个右子节点的父节点大），左右都遍历完了，再输出这个当前节点，同理，输出完当前节点，再看看当前节点有没有左子节点，没有的话，再回到当前节点的父节点，这样以此类推，就能按照从大到小输出，当然我们只要第k大，所以定义一个常量，当到了第k个直接return即可；如下图为我手画的基于示例图的堆栈执行过程；

 

class Solution {
    int count;
    int result = -1;

    public int kthLargest(TreeNode root, int k) {
        count = k;
        kthLargest(root);
        return result;
    }

    public void kthLargest(TreeNode root) {
        if (Objects.nonNull(root)) {
            kthLargest(root.right);
            if (count == 1) {
                result = root.val;
                count--;
                return;
            }
            count--;
            kthLargest(root.left);
        }
    }
}