二叉搜索树第K大节点

问题

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

解答

二叉搜索树的中序遍历（左-根-右）得到升序序列。反过来，反向中序遍历（右-根-左）得到降序序列，第 K 个访问的节点就是第 K 大。

递归实现

function TreeNode(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

function kthLargest(root, k) {
  let count = 0;
  let result = null;

  // 反向中序遍历：右 -> 根 -> 左
  function reverseInorder(node) {
    if (!node || result !== null) return;

    // 先遍历右子树（较大的值）
    reverseInorder(node.right);

    // 访问当前节点
    count++;
    if (count === k) {
      result = node.val;
      return;
    }

    // 再遍历左子树
    reverseInorder(node.left);
  }

  reverseInorder(root);
  return result;
}

迭代实现

function kthLargest(root, k) {
  const stack = [];
  let node = root;
  let count = 0;

  while (node || stack.length) {
    // 一直向右走
    while (node) {
      stack.push(node);
      node = node.right;
    }

    // 弹出并访问
    node = stack.pop();
    count++;
    if (count === k) {
      return node.val;
    }

    // 转向左子树
    node = node.left;
  }

  return null;
}

测试

//       5
//      / \
//     3   6
//    / \
//   2   4

const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);

// 降序：6, 5, 4, 3, 2
console.log(kthLargest(root, 1)); // 6
console.log(kthLargest(root, 3)); // 4

关键点

• BST 中序遍历得到升序，反向中序遍历得到降序
• 反向中序：右 → 根 → 左
• 找到第 K 个节点后立即返回，避免多余遍历
• 时间复杂度 O(k)，最坏 O(n)
• 空间复杂度 O(h)，h 为树高