116. Populating Next Right Point

题目

给定一个完美二叉树，所有子节点都有相同的层级，并且每个父节点都有两个子节点。将同一层级上的节点按从左到右的顺序连接起来。

image.png

解析

如果以递归的方式解决这个问题

1. 当我们传入 1 节点
2. 连接 1 节点的子节点 2，3
3. 递归 2，3 节点

从2,3 节点开始，左右子树分割成了两个不想干的子树，导致 5， 6 节点无法连接在一起。基于次，我们设计另一个递归函数，这个递归函数接受两个节点 2，3。然后仅连接 5,6。并且继续传入 5，6。

递归函数可以写成
f(node) = f(node.left) + f(node.right) + f2(node.left, node.right)

伪代码

f(node)

node.left.next = node.right
f(node.left)
f(node.right)
f2(node.left, node.right)

f2(left, right)

left.right.next = right.left
f2(left.right. right.left)

代码

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    f(root)
    return root
}

func f(node *Node) {
    if node.Left == nil {
        return
    }
    node.Left.Next = node.Right
    f(node.Left)
    f(node.Right)
    f2(node.Left, node.Right)
}

func f2(left *Node, right *Node) {
    if left.Right == nil {
        return
    }
    left.Right.Next = right.Left
    f2(left.Right, right.Left)
}