面试题8：二叉树的下一个节点

从完整中序序列的下一项开始

先预测：在二叉树的中序序列5, 6, 7, 8, 9, 10, 11中，节点8的下一项是9，节点7的下一项是8，节点11没有下一项。若只拿到目标节点指针，怎样不从根重新遍历整棵树就找到这些答案？

这道“二叉树的下一个节点”给每个节点增加一个指向父节点的指针，要求返回该节点在中的下一个节点。这个节点称为中序后继。题目没有说这是一棵二叉搜索树，因此不能比较节点值，答案只由树的结构决定。

中序顺序是“左、根、右”。访问完当前节点后，未访问区域只有两种位置：若有右子树，下一个节点在右子树内部；若没有右子树，就必须回到尚未访问的祖先。作者源码正是把问题分成这两个互斥分支。

有右子树时为何一路向左（最左节点）

设当前节点为node。中序遍历访问node之后会进入它的右子树，而右子树自身仍按“左、根、右”访问。因此右子树中最先出现的节点必然是从右孩子出发不断沿left走到尽头的节点，即。

例如节点8的右孩子是10，10还有左孩子9，所以8的后继是9而不是10。若右孩子本身没有左孩子，例如全右树中的节点2，那么右孩子3就是后继。这里“最左”描述拓扑方向，不意味着它的数值最小。

作者实现保持一个next指针，并在右子树分支中向左扫描：

struct BinaryTreeNode {
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode* parent;
};
 
BinaryTreeNode* getNext(BinaryTreeNode* node) {
    if (node == nullptr) return nullptr;
 
    BinaryTreeNode* next = nullptr;
    if (node->right != nullptr) {
        BinaryTreeNode* cursor = node->right;
        while (cursor->left != nullptr) {
            cursor = cursor->left;
        }
        next = cursor;
    } else {
        BinaryTreeNode* current = node;
        BinaryTreeNode* parent = node->parent;
        while (parent != nullptr && current == parent->right) {
            current = parent;
            parent = parent->parent;
        }
        next = parent;
    }
    return next;
}

第一分支最多下降树高h层。它不需要递归、栈或容器，额外空间为O(1)。即使右子树内部有很多节点，也无需完整遍历，因为中序最先访问的位置只由连续左边确定。

无右子树时沿父节点向上寻找

节点没有右子树时，它自己的子树已经访问完。此时让算法沿祖先链回退。关键不是找到任意父节点，而是找到第一个满足“当前路径从它的左孩子一侧上来”的祖先。

如果current == parent->left，那么父节点尚未被中序访问，父节点就是后继。例如叶子5是6的左孩子，5的后继直接是6。若current == parent->right，说明父节点及父节点的左子树都已经访问过，父节点不可能再次成为后继，必须把current提升为parent继续向上。

这就是。节点7是6的右孩子，所以先越过6；而6是8的左孩子，于是8是7的后继。节点11一路以右孩子身份回到根8，根之上没有父节点，因此11是。

循环不变量是：被跨过的每个parent及其左侧区域都已经访问完，真正的后继只可能在更高处。循环结束有两种原因：找到当前路径来自左分支的父节点，这个父节点就是答案；或父指针变为空，说明不存在后继。

正确性证明要覆盖两个互斥分支

对有右子树的节点，中序规则规定访问当前节点后立即遍历右子树。右子树的第一项是它的最左节点，所以第一分支返回的节点既位于当前节点之后，又不存在更早候选。

对没有右子树的节点，当前节点以下不存在未访问区域。沿父链向上时，只要当前节点是父节点的右孩子，该父节点早已在进入右子树前被访问，不能成为答案；第一个让当前节点位于其左分支的祖先尚未被访问，而且在访问完这条左分支后立刻被访问，所以它是最近后继。若这样的祖先不存在，当前节点位于根的整条最右结束路径上，因而没有后继。

两种情况由node->right是否为空完全划分，没有遗漏也不会重叠。算法只沿一条向下路径或一条向上路径移动，时间复杂度是O(h)，其中h是树高；平衡树为O(log n)，退化树最坏为O(n)，额外空间始终为O(1)。

把两条规则写成有限状态过程

面试现场可以把算法记为三个状态，而不是背一段条件嵌套。状态一“向右进入”：只执行一次，从当前节点进入右孩子；状态二“向左下降”：只要还有左孩子就继续，停点就是答案；状态三“沿父链回退”：当前无右子树时启动，只要自己是父节点的右孩子就越过父节点。前两个状态处理右子树分支，第三个状态处理祖先分支。

这种拆分也能防止变量角色混乱。下降阶段的游标始终位于右子树内部；上爬阶段则同时维护current与parent，因为每提升一层都要重新判断两者的父子关系。若只移动parent而不移动current，下一轮仍拿原节点与更高祖先比较，条件不再表达“当前路径来自哪一侧”。

还可以用一次完整中序遍历作为测试预言机：把节点地址按访问顺序收集，对每个下标i检查getNext(sequence[i])等于下一地址，末项检查为空。预言机实现虽然是O(n)，却与被测局部算法采用不同思路，适合随机生成树和重复值树的性质测试；这样能发现手写少量样例遗漏的深层祖先组合。

父指针是输入契约的一部分

函数局部逻辑很短，但它依赖每条父子链接双向一致：若parent->left == child或parent->right == child，那么child->parent必须回到同一父节点。构造树时只设置孩子指针、忘记设置父指针，会让第二分支提前返回空或跳到错误祖先。

生产代码若接收不可信结构，还要防止父链循环。比如节点的parent错误指向自己，或两个祖先互相指向，原始循环永远不会结束。可以在树构造或反序列化阶段一次性验证无环和双向一致，而不是让每次查询承担整树校验；需要防御性接口时，可增加步数预算或快慢指针检测。

下面的调试校验只验证目标节点经过的局部父链，并用集合拒绝循环：

#include <stdexcept>
#include <unordered_set>
 
BinaryTreeNode* checkedGetNext(BinaryTreeNode* node) {
    std::unordered_set<BinaryTreeNode*> seen;
    for (auto* current = node; current != nullptr;
         current = current->parent) {
        if (!seen.insert(current).second) {
            throw std::invalid_argument("parent cycle");
        }
        if (current->parent != nullptr &&
            current->parent->left != current &&
            current->parent->right != current) {
            throw std::invalid_argument("broken parent link");
        }
    }
    return getNext(node);
}

这个包装器使用O(h)额外空间，不再满足原题的O(1)目标，因此适合边界检查、调试或不可信输入。若树由受控构造器维护不变量，正式查询仍应使用作者的常数空间实现。

没有父指针时需要换取什么

若只有目标节点而没有根指针和父指针，算法无法知道自己处于哪个祖先的左侧或右侧，一般不能确定无右子树节点的后继。额外给出根指针后，可以从根搜索到目标并记录祖先候选，但一般二叉树不能按值定向搜索，最坏要遍历O(n)个节点。

若整棵树是二叉搜索树且值唯一，可以从根按键值下降：每次目标值小于当前值时，把当前节点记为候选并向左；否则向右。那是利用搜索树序的另一道算法，不应混入本题的一般二叉树契约。若允许修改节点结构，父指针把祖先信息分散保存在每个节点，使单次查询只访问与树高相关的路径。

批量查询时还可以先做一次完整中序遍历，将节点按顺序存入数组或建立node → successor映射。预处理时间和空间都是O(n)，之后每次查询平均O(1)。选择父指针、逐次遍历还是预处理，应根据树是否频繁变化、查询次数和内存预算决定。

测试要覆盖形状与分支边界

作者官方源码包含16组断言。第一组完整树以8为根，左右孩子为6和10，叶子为5、7、9、11，逐一验证8→9、6→7、10→11、5→6、7→8、9→10以及11→null。这七个位置覆盖右子树下降、直接父节点、多层上爬和中序末尾。

全左树5←4←3←2验证根5没有后继，而4、3、2的后继都是直接父节点。全右树2→3→4→5验证2、3、4的后继是右孩子，末端5连续上爬后为空。单节点树验证最小非空结构也没有后继。

测试不应只比较节点值；若值重复，值相同不能证明返回了正确对象。应直接比较节点地址或稳定ID。还应单独测试空输入返回空，并在防御性包装器中覆盖断裂父链和父链循环。

#include <cassert>
 
void testCompleteTree() {
    BinaryTreeNode n5{5}, n6{6}, n7{7}, n8{8};
    BinaryTreeNode n9{9}, n10{10}, n11{11};
 
    n8.left = &n6;   n6.parent = &n8;
    n8.right = &n10; n10.parent = &n8;
    n6.left = &n5;   n5.parent = &n6;
    n6.right = &n7;  n7.parent = &n6;
    n10.left = &n9;  n9.parent = &n10;
    n10.right = &n11; n11.parent = &n10;
 
    assert(getNext(&n8) == &n9);
    assert(getNext(&n5) == &n6);
    assert(getNext(&n7) == &n8);
    assert(getNext(&n11) == nullptr);
    assert(getNext(nullptr) == nullptr);
}

本章练习

概念说明

本章核心概念包括：右子树的最左节点，沿父节点向上寻找。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 二叉树的下一个节点是整棵树中序遍历序列中紧跟当前节点的对象。
2. 当前节点有右子树时，后继是右子树的最左节点。
3. 当前节点无右子树时，应沿父节点向上寻找首个来自其左分支的祖先。
4. 连续以右孩子身份上爬到根外，说明当前节点是中序最后节点，返回空。
5. 算法不依赖节点值，也不要求二叉搜索树；比较值会偷换题目条件。
6. 单次查询时间为O(h)、额外空间为O(1)，退化树最坏访问O(n)层。
7. 父指针和孩子指针必须双向一致，非可信结构还要防止父链循环。
8. 官方16组断言通过完整树、全左树、全右树和单节点覆盖两个分支及空后继。

名词解释