116. Populating Next Right Pointers in Each Node

Solution： Iterative 每层遍历，对应连接

思路：Because the input is a perfect binary tree that has complete nodes, the following idea for every level would work:

屏幕快照 2017-09-06 下午7.06.11.png

Time Complexity:O(N) Space Complexity: O(1)

Solution2：dfs 自round1

Time Complexity:O(N) Space Complexity: O(logN) 递归缓存

Solution Code：

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode level_head = root;
        while (level_head != null) {
            TreeLinkNode cur = level_head;
            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;
            }
            level_head = level_head.left;
        }
    }
}

public class Solution {
    public void connect(TreeLinkNode root) {
        dfs(root);
    }
    
    private void dfs(TreeLinkNode root) {
        if(root == null || root.left == null || root.right == null) return;
        
        root.left.next = root.right;
        if(root.next != null) {
            root.right.next = root.next.left;
        }
        
        dfs(root.left);
        dfs(root.right);
    }
}