前言「二叉树的下一个结点」通常指中序遍历in-order traversal中某个结点的后继按照「左、根、右」的顺序访问完整棵树时紧跟在给定结点后面的那个结点。这个问题在面试里经常出现因为它同时考察对遍历顺序的理解和对树结构的利用而不是背一个公式。最常见的错误是把「下一个结点」直接当成「右孩子」。右孩子只是右子树的根中序后继应当是右子树中最左边的结点如果结点没有右子树后继要沿父指针向上找直到某个祖先是其父的左孩子。另一个常见错误是忽略「没有后继」的情况整棵树最后一个结点没有下一个结点函数必须能返回空指针。还有人把「二叉树」与「二叉搜索树」混为一谈前者没有大小关系不能靠比较值来定位后继。本文按三种前提分别讨论结点带父指针、只有根指针、以及树是二叉搜索树的情形。示例以 C17 为基准只使用标准库。一、中序后继的两种情况中序遍历的顺序是先访问左子树再访问根最后访问右子树。对某个结点 x 来说它的后继只可能来自两个方向。情况一x 有右子树。访问完 x 之后下一个进入的是它的右子树而右子树中最先被访问的是最左边的结点。因此后继是「x 的右子树中的最左结点」。注意不是右孩子本身如果右孩子有左子树后继在更深处。情况二x 没有右子树。说明以 x 为根的这棵子树已经访问完毕接下来要回到祖先。沿着父指针向上走只要当前结点是父结点的右孩子就说明父结点也已经访问过因为右子树在根之后继续向上直到遇到一个结点是其父的左孩子那个父结点就是后继。如果一路走到根都没有遇到这种情况说明 x 是整棵树最后一个被访问的结点后继为空。这两种情况合起来构成了带父指针时的完整解法。它的时间复杂度是 O(h)h 为树高情况一沿着左链向下情况二沿着父链向上都不会重复走同一层超过常数次。最坏情况下树退化成链h 等于结点数。二、带父指针的 O(h) 解法先定义结点。父指针用裸指针表示「借用」树的拥有关系由外部容器或根的所有者负责示例中不涉及删除因此不需要unique_ptr。// 适用于 C17#include iostreamstruct Node {int value;Node* parent nullptr;Node* left nullptr;Node* right nullptr;explicit Node(int v) : value(v) {}};Node* leftmost(Node* n) {while (n ! nullptr n-left ! nullptr) {n n-left;}return n;}Node* inorder_successor(Node* node) {if (node nullptr) return nullptr;// 情况一有右子树后继是右子树的最左结点if (node-right ! nullptr) {return leftmost(node-right);}// 情况二无右子树向上找第一个「当前结点是其左孩子」的祖先Node* cur node;Node* p cur-parent;while (p ! nullptr cur p-right) {cur p;p p-parent;}return p;}推演几个边界结点是叶子且是父的左孩子p ! nullptrcur p-right为假循环不进入直接返回父结点。正确因为父结点在左子树访问完后被访问。结点是叶子且是父的右孩子先向上到父若父仍是祖父的右孩子就继续直到某个祖先是左孩子或到达根。返回那个祖先的父结点或者空。结点是整棵树的最右叶一路向上全是右孩子最终p变成空返回空指针。正确。结点是根且没有右子树p为空返回空。正确。结点为空直接返回空调用方不需要额外判空。leftmost里的n ! nullptr判断在传入非空右子树时其实不会用到但保留它可以让函数独立成立避免调用方传空时解引用。三、没有父指针时怎么办如果结点结构里没有parent就不能在 O(h) 内直接向上回溯。此时要分两种前提。一般二叉树只能遍历对任意二叉树没有父指针就无法从结点本身判断它在整棵树中的位置必须从根开始做一次中序遍历记录前一个访问的结点当前结点等于目标时返回下一个。用显式栈可以避免递归深度问题// 适用于 C17#include vectorNode* successor_by_traversal(Node* root, Node* target) {std::vectorNode* st;Node* cur root;Node* prev nullptr;while (cur ! nullptr || !st.empty()) {while (cur ! nullptr) {st.push_back(cur);cur cur-left;}cur st.back();st.pop_back();if (prev target) {return cur;}prev cur;cur cur-right;}return nullptr;}这里用结点地址比较prev target而不是比较value。二叉树允许重复值按值比较可能返回错误的结点。函数的时间复杂度 O(n)空间复杂度 O(h)。如果目标不在树中prev永远不会等于它最终返回空指针调用方若需要区分「没有后继」与「目标不存在」可以额外返回一个状态。二叉搜索树利用大小关系如果树同时是二叉搜索树BST即使没有父指针也可以从根开始按值比较在 O(h) 内找到后继沿路径向下记录最后一个「值大于目标」的结点作为候选走到目标后如果它有右子树后继是右子树最左结点否则候选就是后继。// 适用于 C17要求树是二叉搜索树且值互不相同// leftmost 沿用上一节的实现Node* successor_in_bst(Node* root, Node* target) {Node* cur root;Node* candidate nullptr;while (cur ! nullptr) {if (target-value cur-value) {candidate cur;cur cur-left;} else if (cur-value target-value) {cur cur-right;} else {if (cur-right ! nullptr) {return leftmost(cur-right);}return candidate;}}return nullptr;}这个版本依赖「左子树所有值小于根、右子树所有值大于根」的 BST 性质普通二叉树不满足套用会得到错误结果。值重复时比较无法区分是哪一个结点后继的定义也变得不唯一工程中如果允许重复通常要在结点里加唯一标识或者退回遍历法。前驱的求法与后继完全对称有左子树时取左子树的最右结点没有左子树时向上找「当前结点是父的右孩子」的祖先。写代码时把left与right、与对调即可但要注意别只改一半。常见坑点坑点一把后继当成右孩子。❌return node-right;右孩子有左子树时中序先访问的是左子树后继不是右孩子。✅ 有右子树时返回leftmost(node-right)。坑点二向上回溯的条件写反。❌while (p ! nullptr cur p-left)这样会在错误的层级停下。✅ 只有当前结点是父的右孩子时才继续向上遇到左孩子关系就停。坑点三忘记处理「没有后继」。❌ 一路向上后直接return p-parent;根结点时解引用空指针。✅ 循环以p ! nullptr为条件结束时返回p自然得到空指针。坑点四在普通二叉树上按值比较找后继。❌ 套用 BST 的target-value cur-value逻辑普通二叉树没有大小关系结果错误。✅ 普通二叉树用中序遍历只有确认是 BST 才用值比较。坑点五用值相等判断是不是目标结点。❌if (prev-value target-value)树中有重复值时可能提前返回。✅ 比较结点地址prev target确保是同一个对象。坑点六递归实现中序遍历导致深树栈溢出。❌ 用递归写dfs斜树深度等于结点数。✅ 用std::vector模拟栈或改用带父指针的 O(h) 解法。坑点七leftmost不判空。❌while (n-left ! nullptr) n n-left;传入空指针时直接崩溃。✅ 循环条件写成n ! nullptr n-left ! nullptr。坑点八认为带父指针的解法一定是 O(log n)。❌ 在退化成链的树上仍宣称对数复杂度。✅ 复杂度是 O(h)平衡树才是 O(log n)最坏 O(n)。总结前提方法时间复杂度空间复杂度有父指针右子树最左或向上找左孩子关系O(h)O(1)一般二叉树、无父指针中序遍历并记录前驱O(n)O(h)二叉搜索树、无父指针按值下行并记录候选O(h)O(1)求前驱左右与大小关系对称处理同上同上「下一个结点」的答案藏在遍历顺序里而不是结点的局部结构里。有父指针时向上回溯把「局部」补成了「全局」没有父指针时只能靠一次遍历或 BST 的大小关系重新获得全局信息。写之前先确认三件事树是不是 BST、结点有没有父指针、值是否允许重复。这三点决定了应该用哪一种解法也决定了边界该怎么写。
