题目描述
思路解析动画文字版
记住「顺上一层的 next 链横着走,把孩子接成下一层的 next 链」,下面逐帧套它。dummy 哨兵让「接第一个孩子」和「接后面的孩子」写法统一,省去判空。
什么是 next：next 指针把同一层的节点从左到右串成一条链:每个指向右边一个,最右的指向 null。我们要按层把这些链建出来。
为什么能省队列：关键洞察:建下一层时,要遍历的「当前层」节点,正好被上一层已建好的 next 链串好了。顺着它横向走就行,无需额外队列。第 0 层只有根 50,本身就是起点。
建第 1 层 next 链：开始建第 1 层的 next 链。准备一个 dummy 哨兵,tail 先指着它。cur 顺着第 0 层的链从 50 起,往右一个个看它们的孩子。
接 50 的左孩子 30：cur=50 有左孩子 30,把它接到 tail(dummy)后面,tail 前移到 30。下一层链现在是 dummy → 30。
接 50 的右孩子 80：cur=50 有右孩子 80,把它接到 tail(30)后面,tail 前移到 80。下一层链现在是 dummy → 30 → 80。
第 1 层 next 链建成：第 0 层横向走完了。dummy.next 指向 30,正是第 1 层的头。这一层的 next 链 30 → 80 → null 全部建好,cur 跳到 30 去建下一层。
建第 2 层 next 链：开始建第 2 层的 next 链。准备一个 dummy 哨兵,tail 先指着它。cur 顺着第 1 层的链从 30 起,往右一个个看它们的孩子。
接 30 的左孩子 20：cur=30 有左孩子 20,把它接到 tail(dummy)后面,tail 前移到 20。下一层链现在是 dummy → 20。
接 30 的右孩子 40：cur=30 有右孩子 40,把它接到 tail(20)后面,tail 前移到 40。下一层链现在是 dummy → 20 → 40。
横向走到 80：cur 顺着第 1 层的 next 链走到 80。没有队列,靠的就是上一层连好的 next 一路横向走过来。
80 没有左孩子：cur=80 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → 20 → 40。
接 80 的右孩子 70：cur=80 的右孩子 70 接到 tail(40)后面。注意这一步:40 是 30 的右孩子,70 是 80 的右孩子,它俩父亲不同(30 和 80)但在同一层挨着,所以 tail 把 40.next 连到 70,跨过不同父亲连上,这正是 dummy+tail 串链的威力。
第 2 层 next 链建成：第 1 层横向走完了。dummy.next 指向 20,正是第 2 层的头。这一层的 next 链 20 → 40 → 70 → null 全部建好,cur 跳到 20 去建下一层。
建第 3 层 next 链：开始建第 3 层的 next 链。准备一个 dummy 哨兵,tail 先指着它。cur 顺着第 2 层的链从 20 起,往右一个个看它们的孩子。
20 没有左孩子：cur=20 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
20 没有右孩子：cur=20 的右孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
横向走到 40：cur 顺着第 2 层的 next 链走到 40。没有队列,靠的就是上一层连好的 next 一路横向走过来。
40 没有左孩子：cur=40 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
40 没有右孩子：cur=40 的右孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
横向走到 70：cur 顺着第 2 层的 next 链走到 70。没有队列,靠的就是上一层连好的 next 一路横向走过来。
70 没有左孩子：cur=70 的左孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
70 没有右孩子：cur=70 的右孩子是空的,没有节点可接,tail 保持不动,下一层链还是 dummy → (空)。
没有下一层：第 2 层这几个节点都没有孩子,dummy 后面什么也没接上,dummy.next 是 null。cur 变成 null,整棵树的 next 都建完了。
全部 next 建成：所有 next 指针都填好了:30.next=80、20.next=40、40.next=70,其余指向 null。回头看,我们一层只走一遍、没用任何队列,靠「上一层 next 链当路、dummy+tail 串下一层」就地完成,额外空间 O(1)。
边界:空树直接返回;缺孩子就跳过;最底层建出空链后结束。
两个追问:对比 lc116(完美树有固定公式);对比 BFS(更直观但 O(宽度) 空间)。
参考代码
class Node: def __init__(self, val=0, left=None, right=None, next=None): self.val = val self.left = left self.right = right self.next = nextclass Solution: def connect(self, root: 'Node') -> 'Node': cur = root while cur: dummy = Node(0) tail = dummy while cur: for child in (cur.left, cur.right): if child: tail.next = child tail = child cur = cur.next cur = dummy.next return root复杂度
- 时间：O(n)，每个节点只在「作为某层成员被横向走过」和「作为孩子被接一次」时各被处理常数次,合计线性
- 空间：O(1)，只用 cur、dummy、tail 几个指针,不开队列;next 指针是题目要求的输出、不算额外空间
易错点
面试追问把动画讲成自己的话
追问它和 lc116(完美二叉树版)有什么区别?
追问能用 BFS 队列做吗?和这个解法比如何?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
寻找二叉树的叶子节点
LeetCode 366 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题