LeetCode 285. 二叉搜索树中的中序后继
题目描述
题意分析
给定节点值互不相同的二叉搜索树，以及其中的节点
p，返回中序遍历中紧跟在p后面的节点。若p已经是中序序列最后一个节点，返回空。二叉搜索树的中序结果严格递增，所以这等价于寻找值严格大于
p.val的最小节点。答案必须返回原树中的节点本身，不是只返回值，也不能把p自己作为后继。
解法：沿 BST 下降并保存后继候选
核心思路
[!blue]
从根向下搜索，同时用
answer保存目前找到的后继候选。当前节点的值与p.val的大小关系，可以决定哪一侧还可能出现更合适的答案。当前值大于目标时，它已经满足后继的数值条件，可以先保存。如果还存在更小且仍大于目标的节点，只可能在当前左子树；右子树的值都更大，不会优于已经保存的候选。因此记录当前节点后继续向左。
当前值小于或等于目标时，它自己不是答案，左子树的值也更小，同样可以全部排除；只需向右寻找更大的值。这也包括走到
p本身的情况，仍然继续向右，而不是立即结束。搜索中每次排除的部分，要么全部不大于目标，要么全部不优于已保存的候选。新的合法候选会位于此前候选的左侧范围中，数值自然更小，所以直接替换即可。走到空节点时已经没有可能改进的位置，返回最后候选；从未找到候选则返回空。
解题步骤
- 将答案候选设为空，从根节点开始。
- 当前值严格大于
p.val时，先保存当前节点，再移动到左孩子。- 否则移动到右孩子，继续寻找严格更大的值。
- 走到空节点后返回保存的候选。
代码实现
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode answer = null;
while (root != null) {
if (root.val > p.val) {
answer = root;
root = root.left;
} else {
root = root.right;
}
}
return answer;
}
}
func inorderSuccessor(root *TreeNode, p *TreeNode) (answer *TreeNode) {
for root != nil {
if root.Val > p.Val {
answer = root
root = root.Left
} else {
root = root.Right
}
}
return
}
复杂度分析
- 时间复杂度：$O(h)$，每轮向下一层，只经过一条搜索路径；平衡树为 $O(\log n)$，链状树最坏为 $O(n)$。
- 空间复杂度：$O(1)$，迭代过程只使用当前节点和一个候选引用，不保存完整中序序列。
关键点总结
[!green]
- 中序后继转化成严格大于目标的最小值查询，BST 的大小关系直接提供搜索方向。
- 向左时保留当前合法候选，避免较小子树没有答案时丢掉它。
- 向右时可以排除当前节点及其整个左子树，不会漏掉合法后继。
易错点总结
[!yellow]
- 将严格大于写成大于等于，会把
p自身保存为答案。- 先移动到左孩子再保存候选，可能丢掉当前唯一满足条件的节点。
- 找到某个更大节点就立即返回，它的左子树中可能还有更接近目标的值。
- 只检查
p的右孩子，无法覆盖右子树中的更小节点或祖先提供的后继。- 这套按值导航依赖 BST 和互异节点值，不能把普通二叉树的中序顺序直接等同于数值顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 173. 二叉搜索树迭代器 | 中等 | 中序迭代器能够依次取得后继，本题只查询一次，直接沿 BST 查找无需展开整个序列。 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 同样利用 BST 中序升序性质，第 k 小还需要统计遍历位置，本题用目标值直接导航。 |
| 510. 二叉搜索树中的中序后继 II | 中等 | 中序后继系列。II 提供父指针，可从右子树或向上的祖先链找后继；本题沿根到目标的路径保留候选。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！