填充每个节点的下一个右侧节点指针

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

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

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

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

这里可以学一下怎么跨越连接两颗子树

回想刚才说的，二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，但是如果只依赖一个节点的话，肯定是没办法连接「跨父节点」的两个相邻节点的。

那么，我们的做法就是增加函数参数，一个节点做不到，我们就给他安排两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」：

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    connectTwoNode(root.Left, root.Right)
    return root
}

// h
func connectTwoNode(node1, node2 *Node) {
    if node1 == nil && node2 == nil {
        return
    }
    // 前序遍历
    node1.Next = node2
    connectTwoNode(node1.Left, node1.Right)
    connectTwoNode(node2.Left, node2.Right)
    connectTwoNode(node1.Right, node2.Left)
}