LeetCode 剑指 Offer 54. 二叉搜索树的第k大节点
题目描述
题意分析
给定一棵二叉搜索树和有效排名
k，返回所有节点值按从大到小排列后的第k个值。排名从1开始，题目保证k不超过节点数；返回的是节点值，不是节点对象，也不需要返回前k个节点组成的列表。二叉搜索树保证每个节点的右子树值更大，左子树值更小，可以利用这个顺序寻找排名，无需额外收集并排序全部值。
原有配图中的“从小到大”说明与部分样例输出存在不一致。本篇以题目链接中的第
k大要求为准，按从大到小的顺序计数；不能把配图中的第k小说明直接套入本题。
解法：反向中序遍历计数
核心思路
[!blue]
普通中序按“左子树、根、右子树”访问，会得到升序序列。将顺序反过来，先完整访问右子树，再访问当前根，最后完整访问左子树，就得到降序序列：右侧全部更大，左侧全部更小，各子树内部也遵守同样的顺序。
用栈保存尚未轮到访问的节点。从当前节点一路沿右孩子入栈，直到右侧为空，栈顶才是剩余部分中应当最先访问的最大节点。入栈只是记住以后要回来处理的位置，不表示这个节点已经获得了排名。
弹出栈顶时才真正访问节点，并将剩余排名
k减一。若变成零，当前值就是答案，可以立即返回；否则转向当前节点的左子树，再沿这棵子树的右链入栈，寻找其中最大的下一个候选。待处理祖先仍留在栈中。当前节点的左子树会先于这些祖先完成，再回到更外层继续下降，因此整个过程保持右、根、左的完整降序。找到第
k个后不必再遍历更小的节点，也不需要保存完整有序序列。
解题步骤
- 从根开始，创建一个空栈。
- 沿当前子树的右链不断入栈，直到当前指针为空。
- 弹出栈顶并执行
k--；若k == 0，返回这个节点的值。- 转向弹出节点的左孩子，再重复沿右链入栈的过程。
- 题目保证排名有效，因此一定会在遍历结束前返回答案。
代码实现
class Solution {
public int kthLargest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
// 先登记右侧路径，弹栈时才按从大到小的顺序计数。
while (root != null) {
stack.push(root);
root = root.right;
}
root = stack.pop();
// 找到第几个取决于访问次序，不能在入栈时提前扣减。
if (--k == 0) {
return root.val;
}
root = root.left;
}
return -1;
}
}
func kthLargest(root *TreeNode, k int) int {
stack := make([]*TreeNode, 0)
for root != nil || len(stack) > 0 {
// 先登记右侧路径，弹栈时才按从大到小的顺序计数。
for root != nil {
stack = append(stack, root)
root = root.Right
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 找到第几个取决于访问次序，不能在入栈时提前扣减。
k--
if k == 0 {
return root.Val
}
root = root.Left
}
return -1
}
复杂度分析
- 时间复杂度：$O(h + k)$，
h为树高。找到答案时恰好弹出k个节点，已经入栈但尚未弹出的节点最多有h个，因此总操作数受两者之和约束；最坏为 $O(n)$。- 空间复杂度：$O(h)$，显式栈保存尚未访问的祖先路径。树不保证平衡，不能一律写成 $O(\log n)$。
关键点总结
[!green]
- 第
k大对应右、根、左的降序遍历，完整右子树必须先于根访问。- 只有出栈才算访问，剩余排名在这个时刻递减。
- 找到有效排名即可返回，保留栈中的其他工作而不必继续完成它。
易错点总结
[!yellow]
- 按左、根、右遍历后直接取第
k项，得到的是第k小，方向与题意相反。- 节点一入栈就递减排名，会把尚未处理右侧更大值的节点提前计数。
- 弹栈后忘记转向左孩子，会跳过当前节点左侧仍大于某些祖先的那些值。
- 已经使用降序遍历，又把排名换算为
n - k + 1，会再次反转排名。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 第k小按左根右读取，本题第k大改为右根左；不要直接返回升序第k项。 |
| 173. 二叉搜索树迭代器 | 中等 | 将升序BST迭代器的压栈方向反过来，可从大到小依次读取节点。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！