0116. Populating Next Right Pointers in Each Node ================================================= 题目信息 -------- :题号: 0116. 填充每个节点的下一个右侧节点指针 :难度: Medium :主题: 完美二叉树、层序遍历、横向链、常量空间 :原题: `LeetCode 0116 `_ :重点: 从队列保存整层,推导出完美树的同父与跨父两类连接,并复用已建立的 next 链遍历下一层父节点 题目重述 -------- 给定一棵完美二叉树的根节点 ``root``。每个节点除 ``left``、``right`` 外还有 ``next`` 指针,需要把它设置 为同一层紧邻的右侧节点;每层最右节点的 ``next`` 必须为 ``nullptr``。完成后返回原根节点。 完美二叉树中,每个非叶节点恰有两个孩子,所有叶节点位于同一深度。树中节点总数在 ``0..2^12 - 1`` 范围内,节点值在 ``-1000..1000`` 范围内。进阶目标是只使用常量额外空间。 自建示例 -------- * 三层完美树:``root = [10,4,16,2,6,14,18]``,按 ``#`` 表示层尾时,连接结果为 ``[10,#,4,16,#,2,6,14,18,#]``; * 跨父连接:上例第三层中 ``6.next`` 必须指向 ``14``,不能只连接同一父节点的两个孩子; * 单节点:``root = [7]``,``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* connectPerfectTree(Node* root) { if (!root) { return nullptr; } root->next = nullptr; for (Node* leftmost = root; leftmost->left; leftmost = leftmost->left) { for (Node* current = leftmost; current; current = current->next) { current->left->next = current->right; current->right->next = current->next ? current->next->left : nullptr; } } return root; } public: Node* connect(Node* root) { return connectPerfectTree(root); } }; 题解 ---- 队列保存层边界 ~~~~~~~~~~~~~~ 最直接的正确方法是层序遍历。``connectWithQueue`` 在每轮开始时固定当前层大小,按从左到右顺序弹出节点; ``previous`` 保存本层上一个节点,当前节点到达时令 ``previous->next = node``,层结束后把最后节点连接到空。 队列保证不同深度不会混合,每层相邻节点恰好在连续两次弹出中出现,所以所有 ``next`` 都会设置一次。这个 方案适用于任意二叉树,时间 ``O(n)``,但为了知道当前节点右边是谁,队列最多保存一整层 ``O(w)`` 个节点。 完美树的新信息 ~~~~~~~~~~~~~~ 完美树让下一层的相邻关系只有两种。对当前层父节点 ``current``: .. code-block:: text 同父孩子:current.left.next = current.right 跨父孩子:current.right.next = current.next.left 第二条只在 ``current->next`` 存在时成立;当前父节点若是层尾,它的右孩子也是下一层层尾,应连接 ``nullptr``。完美树保证每个正在处理的父节点都有左右孩子,也保证右侧相邻父节点必有左孩子,因此不需要 搜索“下一个实际存在的孩子”。 这两类关系覆盖全部相邻对:下一层任意两个相邻节点要么共享父节点,要么分别是两个相邻父节点的右孩子与 左孩子。队列中保存整层的目的可以改由当前层已经建立的 ``next`` 链承担。 逐层复用横向链 ~~~~~~~~~~~~~~ ``connectPerfectTree`` 处理某层前保持不变量:该层已经通过 ``next`` 从左到右完整连接,层尾指向空。根层 只有一个节点,显式设置 ``root->next = nullptr`` 后满足基础情况。 内层循环从 ``leftmost`` 开始,沿 ``current = current->next`` 访问当前层全部父节点,同时用上面的两条 规则建立下一层。处理完成后,下一层也形成完整横向链;外层令 ``leftmost = leftmost->left``,进入下一层 最左节点。到达叶层时 ``leftmost->left`` 为空,不再尝试访问孩子。 因此算法并非在使用尚未构造的 ``next``:当前层链在上一轮已经完成,当前轮只写下一层。这个先后关系是 常量空间方案成立的核心不变量。 连接走读 ~~~~~~~~ 对 ``[10,4,16,2,6,14,18]``: .. list-table:: :header-rows: 1 * - 当前父节点 - 同父连接 - ``current.next`` - 跨父或层尾连接 * - 10 - ``4 -> 16`` - 空 - ``16 -> null`` * - 4 - ``2 -> 6`` - 16 - ``6 -> 14`` * - 16 - ``14 -> 18`` - 空 - ``18 -> null`` 处理根后,第二层已有 ``4 -> 16 -> null``,于是下一轮可以从 ``4`` 横向走到 ``16``。在 ``4`` 处通过 ``4.next.left`` 找到 ``14``,正好完成跨父连接 ``6 -> 14``。 分支与主解选择 ~~~~~~~~~~~~~~ 代码始终主动写根和每层尾部的空指针,使结果不依赖节点原有 ``next`` 内容。内层两次赋值顺序可以交换, 因为读取的是当前层父节点的 ``next``,写入的是下一层孩子的 ``next``,两者不冲突。 公开入口采用完美树常量空间方案,因为题目保证正好消除了寻找缺失孩子的需求;队列法仍作为从层序定义出发 的通用基线。若树不是完美树,``current->next->left`` 可能为空甚至不存在,当前两条固定规则便不足以覆盖 下一层,不能直接套用。 复杂度分析 ~~~~~~~~~~ 两种方法都处理每个节点常数次,时间 ``O(n)``。队列法工作空间 ``O(w)``;主解只保存 ``leftmost``、 ``current`` 等常数个指针,额外空间 ``O(1)``。所有连接写入原节点,返回值只是原根指针。