# Populating Next Right Pointers in Each Node
###### tags: `Medium` `Tree`
>question : https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/789/

>reference :

>related problem :
## My Solution
想法 :

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

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    public Node connect(Node root) {
        if(root != null && root.left != null) {
            connectEachLevel(root);
        }
        return root;
    }
    
    private void connectEachLevel(Node root) {
        Node next_root = root.left;
        root.left.next = root.right;
        Node pre_right = root.right;
        root = root.next;
        while(root != null) {
            pre_right.next = root.left;
            root.left.next = root.right;
            pre_right = root.right;
            root = root.next;
        }
        if(next_root.left != null)
            connectEachLevel(next_root);
    }
}

## Other Solution

class Solution {
    public Node connect(Node root) {
        dfs(root, null);        
        return root;
    }
    
    private void dfs(Node curr, Node next) {
        if (curr == null) return;
        curr.next = next;
        dfs(curr.left, curr.right);
        dfs(curr.right, curr.next == null ? null : curr.next.left);
    }
}