LeetCode LCR 053. 二叉搜索树中的中序后继
题目描述
题意分析
给定二叉搜索树和树中的节点
p，返回中序遍历中紧跟在它之后的节点。题目中节点值互不相同，中序顺序又是升序，因此后继就是所有严格大于p.val的节点中值最小的那个；不存在时返回空。
解法：单路径寻找严格后继
核心思路
[!blue]
从根向下搜索，用
answer保存当前找到的最小合法候选。若当前值大于p.val，它可以作为后继，但左子树中还可能有更小的合法值，因此先记录当前节点，再向左寻找。此时无需搜索右子树：其中的值都大于当前值，不会优于已经记录的候选。反之，若当前值小于等于
p.val，当前节点及整棵左子树都不够大，唯一可能的位置就在右子树。每次转向都会排除不合法或不可能更优的区域，剩余的更优候选始终位于当前待查子树。记录过候选后，后续搜索都在它的左子树范围内，之后遇到的合法候选一定更小，可以直接覆盖
answer。走到空节点时已无待查区域，保存的候选就是全局最小严格上界。这是利用有序性排除一侧子树，并不保证每次减少一半节点；访问次数由实际树高决定。
解题步骤
- 将
answer初始化为空，从树根开始。- 当前值严格大于
p.val时，记录当前节点，再转向左孩子。- 当前值小于等于
p.val时，直接转向右孩子。- 当前节点为空时返回
answer。遇到
p本身也要继续向右，不能将它作为自己的后继。若p没有右子树，答案仍可能是途中保存的某个祖先；若它是全树最大节点，就一直没有合法候选，最终返回空。
代码实现
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)$，每次只沿一条边向下，$h$ 为树高；平衡树为 $O(\log n)$，退化成链时为 $O(n)$。
- 空间复杂度：$O(1)$，只保存当前节点和候选指针，不使用递归或栈。
关键点总结
[!green]
- BST 的有序性把中序后继转换成最小严格上界查询。
- 当前值更大时保留候选再左转，当前值不够大时排除整棵左子树再右转。
- 保存候选才能在向下搜索结束后，仍返回位于祖先位置的后继。
易错点总结
[!yellow]
- 后继必须严格大于 p.val，比较不能写成 >=。
- 当前值更大时记录候选并向左寻找更近者，否则向右；第一个候选不一定就是最终答案。
- 后继可能是祖先，不只在 p 的右子树中；最大节点没有后继时返回空。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 173. 二叉搜索树迭代器 | 中等 | 中序迭代器可依次得到后继，本题只问一个节点，沿BST导航更直接。 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 同样利用中序升序性质，原题按名次找节点，本题按目标值寻找最小严格上界。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！