You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

image

Solution：

1. 2个循环
   • 一个用于横向遍历当前层，并连接当前层每个节点的左右子树。
   • 一个用于用于纵向遍历整棵树。
2. maintain3个变量：
   • parent： 当前层当前执行的节点
   • childHead: 下一层的第一个节点
   • prev： 最右一个被连接过的节点。换句话说，prev还没有进行prev.next = ???的操作

                 1
                / \
    parent     2    3
              / \  / \
 childHead   4  5 6   7 
 prev
 
 
 初始，parent = 2；
 childHead = null, prev = null

1. 当childhead == null时，表示第一次进入当前层，需要初始化childHead和prev == parent.left or parent.right。
   当childHead != null时，表示PREV已经存在了，只需要链接prev.next = parent.left or parent.right, 同时 move prev to prev.next (horizontally)。

2. 当parent左右子树都执行了以后，move parent to parent.next 再次重复进行step1，直到当前层全部遍历完，parent为空。

3. 然后重置parent = childHead， childHead = null, prev = null，相当于继续执行下一层。直到整个树全部遍历完成

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val,Node _left,Node _right,Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

/****************

                 1
                / \
    parent     2    3
              / \  / \
 childHead   4  5 6   7 
 prev
 
 
 初始，parent = 2；
 childHead = null, prev = null
 
 1. 当childhead == null时，表示第一次进入当前层，需要初始化childHead和prev == parent.left or parent.right
 当childHead != null时，表示PREV已经存在了，只需要链接prev.next = parent.left or parent.right, 同时 move prev to prev.next (horizontally)
 
 2. 当parent左边子树都执行了以后，move parent to parent.next 再次重复进行step1，直到当前层全部遍历完，parent为空。
 3. 然后重置parent = childHead， childHead = null, prev = null，相当于继续执行下一层。直到整个树全部遍历完成
*****************/
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        
        Node parent = root;
        Node childHead = null;
        Node prev = null;
        
        while (parent != null) {
            
            // loop through current layer
            while (parent != null) {
                if (parent.left != null) {
                    if (childHead == null) {
                        childHead = parent.left;
                        prev = parent.left;
                    } else {
                        prev.next = parent.left;
                        prev = prev.next;
                    }
                }
                
                if (parent.right != null) {
                    if (childHead == null) {
                        childHead = parent.right;
                        prev = parent.right;
                    } else {
                        prev.next = parent.right;
                        prev = prev.next;
                    }
                }
                
                parent = parent.next;
            }
            
            // move to next layer
            parent = childHead;
            childHead = null;
            prev = null;
        }
        
        return root;
    }
}