LeetCode LCR 053. 二叉搜索树中的中序后继
目录
题目描述
题意分析
题目目标：给定二叉搜索树的根和树中的一个节点
p，返回中序遍历中紧跟在p之后的那个节点；若p已经是中序序列的最后一个（即全树最大值），返回空。
核心约束：树是二叉搜索树，中序序列即升序序列，因此"中序后继"等价于"所有严格大于p.val的节点中值最小的那个"。这一步语义转换是整道题的关键——它把一个与遍历顺序相关的定义，翻译成了一个纯粹的值域查询，于是可以直接利用有序性沿树下行，而不必真的做遍历。
边界处理：p是最大值时无后继，必须返回空；p可能没有右子树，此时后继在祖先中；p也可能是根；节点值题目保证互不相同，因此"严格大于"不会产生歧义。
实现取舍：只要能在下行过程中记住"迄今为止见过的、值大于p.val的最小节点"，走到空指针时它就是答案，不需要父指针也不需要栈。
解法：深度优先搜索
核心思路
暴力做法是完整地中序遍历一遍，把节点存进数组再找
p的下一个，或者用一个"上一个访问节点"的变量在遍历中匹配。这样是 $O(n)$ 时间、最坏 $O(n)$ 空间，完全没有用到二叉搜索树的有序性。
把定义翻译成"大于p.val的最小节点"之后，有序性立刻能派上用场：站在某个节点root上，如果root.val > p.val，那么root本身就是一个合法候选（它大于p），但它的右子树里所有值都比它更大，不可能更优，所以应当把它记下来然后转向左子树寻找更小的候选；反之如果root.val <= p.val，那么root及其整棵左子树都不够大，只能转向右子树。
由此确定不变量：每一步下行之后，answer保存的是"在已经排除的部分中，所有大于p.val的节点里值最小的那个"，而尚未探索的子树中若存在更优候选，一定还在当前root所指向的那棵子树里。两个条件合起来保证了走到空指针时answer就是全局最优。
这条路径本质上就是一次二分查找：每次比较把候选范围砍掉一半，路径长度不超过树高，无需回溯也无需额外容器；answer初始为空，天然覆盖了"p是最大值、一次都没记录过候选"的情况。
解题步骤
- 初始化
answer = null，root从树根开始。为什么初值是空：它同时是"尚未找到候选"和"确实不存在后继"两种情况的表示，无需额外标志位。- 循环条件是
root != null，走到空即结束。为什么走到空就能停：下行路径每一步都排除了半棵子树，走到空说明所有可能更优的区域都已被排除。- 当
root.val > p.val时执行answer = root并转向root.left。为什么可以直接覆盖answer而不必比较大小：沿着这条路径每一次记录的候选都严格小于上一次记录的（因为我们转向的是左子树），所以后写入的必然更优。- 为什么此时不去右子树：右子树里的所有值都大于
root.val，而root.val已经大于p.val，它们只会是更差的候选。- 当
root.val <= p.val时直接转向root.right且不记录。为什么用小于等于而不是小于：p本身就在树上，走到p时root.val == p.val，它不是自己的后继，必须继续往右找；写成小于会把p自己记成答案。- 循环结束返回
answer。为什么这就是中序后继：它是所有大于p.val的节点中的最小者，按升序排列恰好排在p之后。- 以
具体用例：树[5, 3, 6, 2, 4, null, 7]（根 5；左子树 3 的孩子是 2、4；右子树 6 的右孩子是 7），查p为节点 4 的后继。从根 5 出发：5 > 4成立，记answer = 5，转向左子树 3。在 3 处：3 <= 4，不记录，转向右子树 4。在 4 处：4 <= 4（正是用小于等于挡住了自己），不记录，转向右孩子，为空。循环结束返回 5，与中序序列2, 3, 4, 5, 6, 7中 4 的下一个一致。再看无后继的情形，查p为节点 7：从 5 出发5 <= 7转右到 6，6 <= 7转右到 7，7 <= 7转右为空，answer始终未被赋值，返回空，正确。
代码实现
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
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)$。凭什么：全程只有
answer和root两个指针，既没有递归调用栈也没有任何容器。
关键点总结
- 遇到"中序前驱/后继"这类与遍历顺序绑定的定义，先把它翻译成值域上的描述（"大于某值的最小节点"），有序性才能真正用起来，这一步转换比后面的代码重要得多。
- "记录候选 + 往更优方向走"是二叉搜索树上求上下界的通用模板：找后继就在大于时记录并左转，找前驱则在小于时记录并右转，两者完全对称。
- 候选可以无条件覆盖而不必比较，靠的是"沿路径记录的候选单调变优"这一性质；能说清这一点，才算真正理解了为什么不需要额外的取最小操作。
- 比较符号里的等号位置决定了
p自身是否会被误当成答案，凡是"严格大于/严格小于"的题目都要专门检查这一处。- 面试视角：面试官常从"如果节点带父指针怎么办"切入。带父指针时的经典解法是——
p有右子树就取右子树的最左节点，否则沿父指针上行直到某个节点是其父亲的左孩子。能对比"值域二分（不需要父指针、$O(h)$ 且 $O(1)$ 空间）"与"指针上行"两种做法，并指出前者还能处理p不在树上的推广情形，是这题的高分答法。
易错点总结
- 错误写法：判断条件写成
root.val >= p.val→ 查节点 4 的后继时走到 4 自己就被记成候选，返回 4 而不是 5，节点成了自己的后继。- 错误写法：
root.val > p.val分支里转向右子树 → 树[5, 3, 6]查 3 的后继时从 5 转向 6，返回 6 而不是 5，跳过了更优候选。- 错误写法：
root.val <= p.val分支里也记录answer→ 查 4 的后继时 3 被记下，返回 3 这个比p还小的节点。- 错误写法：把
answer的更新写成"仅当比现有候选更小才更新"却漏掉空值判断 → 首次记录时对空指针取val，直接空指针异常。- 错误写法：用
p == root这种引用比较代替值比较，并假设p一定在树上 → 若测试用例传入的是值相同但对象不同的节点，判断永远不成立，循环一路右转返回空。- 错误写法：找到
p后直接返回它右子树的最左节点 → 树[5, 3, 6, 2, 4]查 4 的后继时 4 没有右子树，该写法返回空，而正确答案是祖先 5。- 错误写法：改成完整中序遍历并用"上一个节点等于
p就返回当前"的写法，却忘记p是最大值的情形 → 遍历结束后没有返回语句或返回了未初始化的值，抛异常或返回错误节点。- 错误写法：循环条件误写成
root != null && answer == null→ 一旦记录了第一个候选就停止下行，树[5, 3, 6, 2, 4]查 2 的后继时返回 5 而不是 3。- 错误写法：以为答案一定在
p的子树里，只在子树内搜索 →p是某棵左子树的最大节点时后继在祖先方向，该写法一律返回空。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 700. 二叉搜索树中的搜索 | 简单 | 精确匹配的下行查找，无需维护候选 |
| 701. 二叉搜索树中的插入操作 | 中等 | 同样沿有序性下行，终点是空位而非候选 |
| 235. 二叉搜索树的最近公共祖先 | 中等 | 用值域区间判断分叉点，一次下行即可定位 |
| 230. 二叉搜索树中第 K 小的元素 | 中等 | 按名次而非按值定位，需要中序计数或子树规模 |
| 173. 二叉搜索树迭代器 | 中等 | 连续求后继的场景，用栈把中序状态持久化更划算 |
| 783. 二叉搜索树节点最小距离 | 简单 | 关注中序相邻两项之差，需维护前驱值 |