面试题54_二叉搜索树的第k大节点.md

面试题 54 ：二叉搜索树的第 K 大节点

---

leetcode-cn 题目地址

📗difficulty：Easy

🎯Tags：

• 树
• 深度优先搜索

---

1. 题目描述📃

给定一棵二叉搜索树，请找出其中第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 ≤ 二叉搜索树元素个数

---

2. 解题思路💡

反向思考

这个想法来自于 一道题目，找到链表的倒数第 k 个节点（最优解是快慢指针）。一种朴素的想法是，得到链表的总长度 l，那么倒数第 k 个，就是正数第 l - k + 1 个。

这里第一次使用中序遍历，获得节点总数。然后再一次使用中序遍历，因为中序遍历可以获得一个二叉搜索树的 从小到大的序列，才能获得“倒数第 k 大的数”。

代码实现

public class Solution1 {
    int nodeSum = 0;
    int m = 0;
    int mTh = 0;
    int res = 0;

    public int kthLargest(TreeNode root, int k) {
        countNodeSum(root);
        mTh = nodeSum - k + 1;
        findMthNode(root);
        return res;
    }

    public void countNodeSum(TreeNode root) {
        if (root == null) {
            return;
        }
        countNodeSum(root.left);
        nodeSum++;
        countNodeSum(root.right);
    }

    public void findMthNode(TreeNode root) {
        if (root == null || m == mTh) {
            return;
        }
        findMthNode(root.left);
        m++;
        if (m == mTh) {
            res = root.val;
        }
        findMthNode(root.right);
    }
}

复杂度分析

• 时间复杂度：O(n) 。最多需要遍历 2 次树。
• 空间复杂度：O(n) 。最坏情况下，在树退化为单链表的情况下，递归栈需要存入整个链表。

---

中序遍历的“倒序”

如果先访问二叉搜索树的右子树，然后是根节点，然后是左子树，那么可以得到这颗二叉搜索树的降序序列。正数的第 k 大也就是要求的“倒数第 k 大”。

如果突破了 先、中、后 序的钳制，将其看成是 DFS，那么问题就简单了。

则需要完成树的遍历的一次“思想解放”。

递归的 代码实现

int idx = 0;
int res = 0;

public int kthLargest(TreeNode root, int k) {
    dfs(root, k);
    return res;
}

public void dfs(TreeNode root, int k) {
    if (root == null || idx == k) {
        // 提前结束
        return;
    }
    // 先右 
    dfs(root.right, k);
    if (++idx == k) {
        res = root.val;
    }
    // 后左
    dfs(root.left, k);
}

迭代的 代码实现

public int kthLargest(TreeNode root, int k) {
    int idx = 0;
    int res = 0;
    Deque<TreeNode> stack = new LinkedList<>();
    while (root != null || !stack.isEmpty()) {
        // 向右走到底
        while (root != null) {
            stack.offerLast(root);
            root = root.right;
        }
        root = stack.pollLast();
        if (++idx == k) {
            return root.val;
        }
        // 处理左子树，只需要改变指针即可
        root = root.left;
    }
    return res;
}

复杂度分析

• 时间复杂度：O(n) 。最多需要遍历 1 次树。
• 空间复杂度：O(n) 。最坏情况下，但树退化为单链表的情况下，递归栈需要存入整个链表。

---

3. 总结🎯

考察对树的遍历的掌握情况，需要对三个经典的遍历有一定的认识，同时了解 二叉搜索树 的性质，此外，对 DFS 也需要掌握牢靠，才能发掘出最优解。