06、填充每个节点的下一个右侧节点指针

二叉树的 left、right 连接父子节点，next 则把同一层的节点从左到右串起来。本题的关键是：下一层的横向连接，可以借助当前层已经建立的连接完成。

问题与目标

LeetCode 116：填充每个节点的下一个右侧节点指针的输入是完美二叉树：每个非叶子节点都有两个孩子，所有叶子在同一层。最右节点的 next 为 nullptr。

输入：[1,2,3,4,5,6,7]
连接：第1层 1 → 空
      第2层 2 → 3 → 空
      第3层 4 → 5 → 6 → 7 → 空

不要把本题的前提扩展到任意二叉树。现有右侧节点指针 II处理的是第 117 题，缺失孩子时不能直接套本题公式。

两种连接，覆盖同一层的所有相邻节点

假设当前父节点是 parent：

1. 同一个父节点下：parent->left->next = parent->right。
2. 跨两个相邻父节点：如果 parent->next 存在，parent->right->next = parent->next->left。

例如先建立 2 → 3，处理节点 2 时就能从 2->next 找到节点 3，再把 5 接到 6。这正是跨父连接的桥梁。

为什么可以不使用队列

根层只有一个节点，已天然可遍历。处理根后，第二层建立 2 → 3；沿这条 next 链就能遍历第二层，同时建立第三层。每处理完一层，让 level_start 向左孩子下降一次。

到叶子层时，不再有下一层需要连接，循环结束。这里没有用递归，也没有偷偷把层节点保存到容器里。

C++17 实现

struct Node {
  int val = 0;
  Node* left = nullptr;
  Node* right = nullptr;
  Node* next = nullptr;
};

class Solution {
 public:
  Node* connect(Node* root) {
    if (root == nullptr) return nullptr;
    root->next = nullptr;
    for (Node* level_start = root; level_start->left != nullptr;
         level_start = level_start->left) {
      for (Node* parent = level_start; parent != nullptr; parent = parent->next) {
        parent->left->next = parent->right;
        parent->right->next = parent->next == nullptr ? nullptr : parent->next->left;
      }
    }
    return root;
  }
};

复杂度与边界

每个非叶子节点被处理一次，时间 O(n)；只有两个遍历指针，额外空间 O(1)。空树直接返回空；单节点树保留 next == nullptr。

输入必须满足完美二叉树的前提。本文没有通过空指针检查把它包装成适用于所有树的通用算法。

常见误区

只连接同父孩子会漏掉 5 → 6；在当前层尚未连好时就依赖它遍历下一层，会提前中断。面试时可以先解释带队列的层序遍历，再说明本实现怎样利用树形前提消除队列。