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

题意：

解题思路：

思路：
   1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL
1. 从根节点出发，每次遍历一层，遍历从左到右的顺序执行，对应每个节点，先让左儿子指向右儿子，然后让右儿子指向下一个节点的左儿子。最后让这一层最右侧的节点指向NULL。
2. 遍历到叶节点所在的层为止；
模拟过程：
* 第一步，遍历根节点，我们让根节点的左儿子指向右儿子，即让2指向3；
* 第二步，从左到右遍历第二层，先遍历2，让2的左儿子指向右儿子，即让4指向5，再让2的右儿子指向下一个节点的左儿子，即5指向6；然后遍历3，依次类推；
* 第三步，我们发现第三层已经是叶节点，算法终止；
时间复杂度分析：每个节点仅会遍历一次，遍历时修改指针的时间复杂度是 O(1)，所以总时间复杂度是 O(n)。

PHP代码实现：

/**
 * Definition for a Node.
 * class Node {
 *     function __construct($val = 0) {
 *         $this->val = $val;
 *         $this->left = null;
 *         $this->right = null;
 *         $this->next = null;
 *     }
 * }
 */
class Solution {
    /**
     * @param Node $root
     * @return Node
     */
    public function connect($root) {
        return $this->connectInteration($root);
        if ($root == null) return null;
        if ($root->left != null) {
            $root->left->next = $root->right;
            if ($root->next != null) {
                $root->right->next = $root->next->left;
            }
        }
        $this->connect($root->left);
        $this->connect($root->right);
        return $root;
    }
    function connectInteration($root) {
        $pre = $root;
        while ($pre != null) {
            $cur = $pre;
            while ($cur != null) {
                if ($cur->left != null) $cur->left->next = $cur->right;
                if ($cur->right != null && $cur->next != null) $cur->right->next = $cur->next->left;
                $cur = $cur->next;//同层移动
            }
            $pre = $pre->left;  //移到下层
        }
        return $root;
    }
}

GO代码实现：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */
func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    if root.Left == nil && root.Right == nil {
        return root
    }
    if root.Left != nil {
        root.Left.Next = root.Right
    }
    if root.Right != nil && root.Next != nil {
        root.Right.Next = root.Next.Left
    }
    connect(root.Left)
    connect(root.Right)
    return root
}
func connectInteration(root *Node) *Node {
    if root == nil {
        return nil
    }
    pre := root
    for pre.Left != nil {
        cur := pre
        for cur != nil {
            cur.Left.Next = cur.Right //左节点连接右节点
            if cur.Next != nil {
                cur.Right.Next = cur.Next.Left //右节点 连接 邻居左节点
            }
            cur = cur.Next //同层移动
        }
        pre = pre.Left //移到下层
    }
    return root
}