AcWing 刷题笔记：18. 二叉树的下一个节点
这道题给定一个二叉树中的单个节点，要求找出它在中序遍历序列中的下一个节点（后继）。
关键是：只给了单个节点和它的指向链接（左、右、父节点），拿不到全局树的结构。这相当于一个线索二叉树的应用场景。
问题分析
给定节点 p，要找它的中序后继，分两种情况讨论：
情况 1：p 有右子树
- 中序遍历中，p 之后是其右子树的最左节点。
- 向右走一步，然后持续向左，找到最左的节点。
情况 2：p 没有右子树
- 需要向上查找父节点。
- 如果 p 是父亲的左子树，则父亲就是后继。
- 如果 p 是父亲的右子树，继续向上找，直到某个节点是其父亲的左子树。
关键思路图
代码实现
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
// 情况 1：p 有右子树，找右子树的最左节点
if (p->right) {
p = p->right;
while (p->left) p = p->left;
return p;
}
// 情况 2：p 没有右子树，向上找父节点
// 直到当前节点是父节点的左子树，则该父节点就是后继
while (p->father && p == p->father->right) {
p = p->father;
}
return p->father;
}
};复杂度分析
- 时间：O(h)，h 是树的高度，最坏 O(n)
- 空间：O(1)
易错点
- 节点比较：注意是
p == p->father->right（判断是否是父亲的右子树），不是p != p->father->left。 - 向上查找终止：要同时检查
p->father存在且 p 是右子树，才继续向上。 - 空指针处理：返回
p->father可能为 nullptr（表示 p 是整个树的最右节点，无后继）。
线索二叉树的启示
这道题本质上是在利用二叉树本身的链接关系（父子指针）来进行遍历。如果想更高效地遍历，可以提前把树”线索化”（在空指针处存储前驱/后继），这样就无需递归或栈了。
总结
这题通过分情况讨论和向上查找，完整展示了中序遍历后继的求法。重点是理解两种情况的递推关系，以及向上回溯时的停止条件。掌握这个思路，后续的树形遍历问题都不是问题！
