题目

给定一个二叉树

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
"""
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':
    # 每次处理当前节点的子节点的 next 指针
    # head 指向 cur 下一层的开头
    cur, head, tail = root, None, None
    while cur:
        while cur:
            if cur.left:
                if not head:
                    head = cur.left
                    tail = cur.left
                else:
                    tail.next = cur.left
                    tail = tail.next
            if cur.right:
                if not head:
                    head = cur.right
                    tail = cur.right
                else:
                    tail.next = cur.right
                    tail = tail.next
            cur = cur.next
        # 下一行
        cur = head
        head, tail = None, None
    return root

• 空间复杂度
• 参考 leetcode方案

方案三（递归，参考leetcode）

def connect(root: 'Node') -> 'Node':
    if not root:
        return None
    if root.left and root.right:
        root.left.next = root.right
    tmp = root.right or root.left
    nx = root.next
    while nx and tmp:
        if nx.left:
            tmp.next = nx.left
            break
        elif nx.right:
            tmp.next = nx.right
            break
        else:
            nx = nx.next
    self.connect(root.right)
    self.connect(root.left)
    return root

• 重点还是如何找到递归子问题
• 原理同上一个题目，只是如何链接中间节点的判断变得复杂一些了而已

原文