剑指Offer
TypeScript
TypeScript

二叉搜索树的第 k 大的节点

题目描述

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

示例 1：

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

示例 2：

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

解题基本知识

二叉搜索树（Binary Search Tree）又名二叉查找树、二叉排序树。它是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

解法一： 递归

在线链接

利用二叉搜索树的特性进行中序遍历。先遍历左节点，然后根节点，最后遍历右节点，得到的是一个递增序列，那么序列的倒序为递减序列。因此这道题我们可以转变为求二叉搜索树中序遍历倒序的第 k 个数。

解法图示

1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val) {
4 *     this.val = val;
5 *     this.left = this.right = null;
6 * }
7 */
8/**
9 * @param {TreeNode} root
10 * @param {number} k
11 * @return {number}
12 */
13const kthLargest = (root, k) => {
14  let res = null; // 初始化返回值
15  // 因为需要倒序第 k 个，所以处理是右节点，根节点，然后左节点
16  const dfs = (root) => {
17    if (!root) return; // 如果当前节点为 null，本轮处理结束
18    dfs(root.right); // 开始处理右节点
19    if (k === 0) return; // k 值 为 0，代表已经处理的节点超过目标节点，本轮处理结束
20    if (--k === 0) {
21      // 当 k 值 减 1 为 0，表示已经到了我们想要的 k 大 节点，保存当前值
22      res = root.val;
23    }
24    dfs(root.left); // 处理左节点
25  };
26  dfs(root); // 从初始化节点开始处理
27  return res;
28};

复杂度分析：

  • 时间复杂度 O(N)：无论 k 的值大小，递归深度都为 N，占用 O(N) 时间。

  • 空间复杂度 O(N)：无论 k 的值大小，递归深度都为 N，占用 O(N) 空间。

解法二： 迭代

在线链接

思路还是二叉树的中序遍历，利用栈的方式进行遍历。

解法图示

1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val) {
4 *     this.val = val;
5 *     this.left = this.right = null;
6 * }
7 */
8/**
9 * @param {TreeNode} root
10 * @param {number} k
11 * @return {number}
12 */
13var kthLargest = function (root, k) {
14  if (!root) return 0;
15  // 声明储存栈
16  const stack = [];
17  // 判断当前栈否有节点和当前遍历节点位置
18  while (stack.length || root) {
19    while (root) {
20      // 往栈里添加当前节点，同时切换为右节点处理
21      stack.push(root);
22      root = root.right;
23    }
24    // 取出当前栈顶元素，根据添加的顺序，当前元素是栈内最大的
25    const cur = stack.pop();
26    k--;
27    if (k === 0) return cur.val;
28    // 切换为左节点处理
29    root = cur.left;
30  }
31  return 0;
32};

  • 时间复杂度 O(N)：需要遍历整棵树一次，复杂度为 O(N)

  • 空间复杂度 O(N)：需要额外空间栈进行储存树，复杂度为 O(N)

参考资料

  1. 剑指 offer
目录