给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

  1. struct Node {
  2.   int val;
  3.   Node *left;
  4.   Node *right;
  5.   Node *next;
  6. }

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
image.png
初始状态下，所有 next 指针都被设置为 NULL。

提示：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

解法一：迭代

迭代完成所有next的连接。从顶层开始，连接每一层每个节点的左右节点，并连接cur.right与cur.next.left。注意同层链表的尾边界。

  1. class Solution:
  2.     def connect(self, root: 'Node') -> 'Node':
  3.         p = cur = root
  4.         while p and p.left:
  5.             while cur:
  6.                 cur.left.next = cur.right
  7.                 if cur.next:
  8.                     cur.right.next = cur.next.left
  9.                 cur = cur.next
  10.             p = cur = p.left
  11.         return root

解法二：先序遍历

这个方法很神奇，按先序遍历的顺序，每个当前节点把它的左右孩子以及右孩子的右侧节点连接起来就可以了。

  1. class Solution:
  2.     def connect(self, root: 'Node') -> 'Node':
  3.         if root and root.left:
  4.             root.left.next = root.right
  5.             root.right.next = root.next.left if root.next else None
  6.             self.connect(root.left)
  7.             self.connect(root.right)
  8.         return root

解法三：后序遍历

比上面一个递归解法容易理解，不依赖先序遍历的特殊顺序，子问题是连接左右独立的子树。
子问题：将左子树的右边缘与右子树的左边缘逐层连接
退出条件：root为空，或root的左右子树为叶子节点

  1. class Solution:
  2.     def connect(self, root: 'Node') -> 'Node':
  3.         if root and root.left:
  4.             p = self.connect(root.left)
  5.             q = self.connect(root.right)
  6.             while p and q:
  7.                 p.next = q
  8.                 p, q = p.right, q.left
  9.         return root

解法四：先序遍历II

改写解法二，先连接左子树的右边缘和右子树的左边缘，然后再递归左右子树，可变成尾递归。

  1. class Solution:
  2.     def connect(self, root: 'Node') -> 'Node':
  3.         def preorder(root):
  4.             if root and root.left:
  5.                 p, q = root.left, root.right
  6.                 while p and q:
  7.                     p.next = q
  8.                     p, q = p.right, q.left
  9.                 self.connect(root.left)
  10.                 self.connect(root.right)
  11.         preorder(root)
  12.         return root

解法五：层次遍历

该方法不符合题目要求的空间复杂度。利用队列实现层次遍历(102. 二叉树的层序遍历)。

解法六：迭代II

依然是层次遍历。普通层次遍历需要从队列中取可用的节点，并将其左右孩子加入队列。而本题中当前层已经是一个链表，遍历链表是O(1)空间复杂度。因此利用当前层已经连接好的链表（这是控制空间复杂度的关键），使用尾插法逐一连接下层的节点。该解法同样适用于 117. 填充每个节点的下一个右侧节点指针 II。

同时该解法也是解法一的衍生。解法一并未保留上层信息，因此只能处理满二叉树的情况。

  1. class Solution:
  2.     def connect(self, root: 'Node') -> 'Node':
  3.         head = root # head表示当前层的链表头
  4.         while head: # 每次循环连接当前层的下一层
  5.             dummy = tail = Node(0) # dummy.next为下一层的头部
  6.             curr = head
  7.             while curr: # 遍历当前层（已经连接），将下一层用尾插法连接
  8.                 if curr.left:
  9.                     tail.next = curr.left
  10.                     tail = tail.next
  11.                 if curr.right:
  12.                     tail.next = curr.right
  13.                     tail = tail.next
  14.                 curr = curr.next
  15.             head = dummy.next
  16.         return root