package code;
/*
 * 116. Populating Next Right Pointers in Each Node
 * next
 * Medium
 * Tree, Depth-first Search
 * next
 * Tips
 */
public class lc116 {
    public class TreeLinkNode {
        int val;
        TreeLinkNode left, right, next;
        TreeLinkNode(int x) { val = x; }
    }
    public void connect(TreeLinkNode root) {
        if(root==null) return;
        helper(root.left, root.right);
    }

    public void helper(TreeLinkNode root1, TreeLinkNode root2){//
        if( root1==null || root2==null ) return;
        root1.next = root2;
        helper(root1.left, root1.right);
        helper(root1.right, root2.left);    //
        helper(root2.left,root2.right);
    }

    public void connect2(TreeLinkNode root) {
        while(root!=null){
            TreeLinkNode start = root;
            while(start!=null){
                if(start.left!=null){
                    start.left.next = start.right;  //next
                    if(start.next!=null){
                        start.right.next = start.next.left;
                    }
                }
                start = start.next;
            }
            root = root.left;
        }
    }
}