0117. Populating Next Right Pointers in Each Node II =================================================== 题目信息 -------- :题号: 0117. 填充每个节点的下一个右侧节点指针 II :难度: Medium :主题: 一般二叉树、层序遍历、横向链、虚拟头节点 :原题: `LeetCode 0117 `_ :重点: 固定孩子公式在稀疏树中失效后,改为扫描当前层并按出现顺序串联下一层所有非空孩子 题目重述 -------- 给定一棵普通二叉树的根节点 ``root``。每个节点还有一个 ``next`` 指针,需要令它指向同一层紧邻的右侧 非空节点;本层最右节点的 ``next`` 必须为 ``nullptr``。树可以任意缺少左孩子或右孩子,完成后返回原根。 树中节点总数在 ``0..6000`` 范围内,节点值在 ``-100..100`` 范围内。进阶目标是只使用常量额外空间, 不能用与层宽成正比的辅助队列作为最终方案。 自建示例 -------- * 跨过空孩子:``root = [8,4,12,null,6,10,null,5,null,null,11]``,用 ``#`` 表示层尾时,结果为 ``[8,#,4,12,#,6,10,#,5,11,#]``; * 只有右孩子:``root = [1,null,2,null,3]``,每层只有一个节点,三个 ``next`` 都应为空; * 单节点:``root = [7]``,返回原节点且 ``next == nullptr``; * 空树:``root = []``,返回 ``nullptr``。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: Node* connectWithQueue(Node* root) { if (!root) { return nullptr; } std::queue pending; pending.push(root); while (!pending.empty()) { const int levelSize = static_cast(pending.size()); Node* previous = nullptr; for (int count = 0; count < levelSize; ++count) { Node* node = pending.front(); pending.pop(); if (previous) { previous->next = node; } previous = node; if (node->left) { pending.push(node->left); } if (node->right) { pending.push(node->right); } } previous->next = nullptr; } return root; } Node* connectWithExistingLevels(Node* root) { if (!root) { return nullptr; } root->next = nullptr; Node* levelStart = root; while (levelStart) { Node dummy(0); Node* tail = &dummy; for (Node* current = levelStart; current; current = current->next) { if (current->left) { tail->next = current->left; tail = tail->next; } if (current->right) { tail->next = current->right; tail = tail->next; } } tail->next = nullptr; levelStart = dummy.next; } return root; } public: Node* connect(Node* root) { return connectWithExistingLevels(root); } }; 题解 ---- 通用队列基线 ~~~~~~~~~~~~ ``connectWithQueue`` 按层弹出节点,用 ``previous`` 把当前节点接在本层上一个节点之后,层末显式连接空指针; 同时按左、右顺序把非空孩子加入下一层。层大小快照保证连接不会跨越深度。 这版对任意二叉树都正确,因为队列显式保存了下一层所有实际节点及其左右顺序。代价是最大层宽为 ``w`` 时, 需要 ``O(w)`` 辅助空间。要达到常量空间,必须让已经写入树中的 ``next`` 自己承担横向遍历通道。 固定公式失效 ~~~~~~~~~~~~ 完美树中可以固定连接 ``current.left -> current.right``,再连接 ``current.right -> current.next.left``。普通树中三处节点都可能缺失:当前父节点可能只有一个孩子,右侧 相邻父节点也可能没有左孩子,最近的下一层节点甚至位于若干父节点之后。 因此问题不再是计算两个固定字段,而是:沿当前层从左到右扫描所有父节点,把遇到的非空孩子按“每个父节点 先左后右”的顺序组成一条新链。这个孩子序列恰好就是下一层从左到右的实际节点序列,空槽位自然被跳过。 虚拟头与链尾 ~~~~~~~~~~~~ ``connectWithExistingLevels`` 使用栈上的虚拟节点 ``dummy`` 和指针 ``tail`` 构造下一层: .. code-block:: text tail->next = child tail = child ``tail`` 初始指向 ``dummy``,所以第一个非空孩子自动写入 ``dummy.next``;后续孩子依次接到真实链尾,不必 为“这是第一个孩子”单独分支。当前层扫描完后,``dummy.next`` 是下一层起点,``tail->next = nullptr`` 明确封闭层尾。 若当前层全是叶节点,没有发现任何孩子,``tail`` 仍指向虚拟节点,置空操作让 ``dummy.next`` 保持空, 随后 ``levelStart`` 变为空并结束。虚拟节点只在当前循环栈帧中辅助构链,不会进入返回树。 逐层不变量 ~~~~~~~~~~ 处理某层前,该层已由 ``next`` 从 ``levelStart`` 连到层尾空指针。根层通过显式设置 ``root->next = nullptr`` 建立基础情况。内层沿这条链扫描父节点并完成下一层;外层再令 ``levelStart = dummy.next``,复用刚生成的链。 每个非空孩子只会在其唯一父节点处被发现一次。父节点顺序从左到右,同一父节点先追加左孩子再追加右孩子, 所以新链既不重复也不遗漏,并保持层内顺序。算法只沿本轮已经重建完成的当前层链移动,不会依赖下一层节点 原有的旧 ``next`` 值。 稀疏层走读 ~~~~~~~~~~ 对 ``[8,4,12,null,6,10,null,5,null,null,11]``: .. list-table:: :header-rows: 1 * - 当前层父节点 - 发现的非空孩子 - 构造中的下一层链 * - 8 - 4、12 - ``4 -> 12`` * - 4 - 6 - ``6`` * - 12 - 10 - ``6 -> 10`` * - 6 - 5 - ``5`` * - 10 - 11 - ``5 -> 11`` 节点 ``5`` 与 ``11`` 的父节点之间存在多个空孩子位置,但构链只处理实际节点,因此它们直接成为同层相邻 节点。每轮结束再写层尾空指针,得到 ``5 -> 11 -> null``。 主解与复杂度 ~~~~~~~~~~~~ 公开入口采用虚拟头与链尾方案。与队列法相比,队列中的“下一层节点序列”被直接写进节点的 ``next`` 字段; 状态只剩当前层起点、当前父节点、虚拟头和链尾几个指针。 每个节点作为孩子追加一次,并在下一轮作为父节点扫描一次,时间 ``O(n)``。队列基线空间 ``O(w)``;主解 除节点已有的 ``next`` 字段外只用常数个指针,额外空间 ``O(1)``。所有修改发生在原节点上。