题目

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

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例：

方案一（层序遍历，广度优先搜索）

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
def connect(root: 'Node') -> 'Node':
    if not root:
        return None
    queue = [root]
    while queue:
        length = len(queue)
        for i in range(length):
            if i != length - 1:
                queue[i].next = queue[i + 1]
            if queue[i].left:
                queue.append(queue[i].left)
            if queue[i].right:
                queue.append(queue[i].right)
        queue = queue[length:]
    return root

换一个写法

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None

        deque = collections.deque([root])
        while deque:
            length = len(deque)
            self.connect_one_layer(deque)
            for i in range(length):
                node = deque.popleft()
                if node.left:
                    deque.append(node.left)
                if node.right:
                    deque.append(node.right)
        return root

    def connect_one_layer(self, nodes):
        for i in range(len(nodes) - 1):
            nodes[i].next = nodes[i + 1]

方案二（递归）

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
def connect(root: 'Node') -> 'Node':
    if not root:
        return None

    # 将 2,4,5 -> 3,6,7 看成一个整体
    left = root.left
    right = root.right
    while left:
        left.next = right
        # 连接上图中 5 -> 6 之间的指针
        left = left.right
        right = right.left

    self.connect(root.left)
    self.connect(root.right)
    return root

• 最主要的点是如何连接上图中的 5 -> 6 之间的指针；
• 如何将问题分解成相同的子问题是递归的关键；

原文