Leetcode/F家微软--117. Populating Next Right Pointers in Each Node II(Iteration or BFS)

117. Populating Next Right Pointers in Each Node II
medium
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Microsoft Bloomberg Facebook

思路1: use BFS, easy but not constant space
Complexity: time O(N) space O(N) - queue

public void connect(TreeLinkNode root) {
        if(root == null)return;
        Queue<TreeLinkNode> nodes = new LinkedList<>();
        nodes.offer(root);
        while(!nodes.isEmpty()){
            int size = nodes.size();
            for(int i = 0; i < size; i++){
                TreeLinkNode cur = nodes.poll();
                TreeLinkNode n = null;
                if(i < size - 1){
                    n = nodes.peek();
                }
                cur.next = n;
                if(cur.left != null)nodes.offer(cur.left);
                if(cur.right != null)nodes.offer(cur.right);
            }
            
        }
    }

思路2： Iteration - use dummy node to keep record of the next level's root to refer
             pre travel current level by referring to root in the level above
Complexity: time O(N) space O(1)

public void connect(TreeLinkNode root) {
        TreeLinkNode dummy = new TreeLinkNode(0);
        TreeLinkNode pre = dummy;//record next root
        while(root != null){
            if(root.left != null){
                pre.next = root.left;
                pre = pre.next;
            }
            if(root.right != null){
                pre.next = root.right;
                pre = pre.next;
            }
            root = root.next;//reach end, update new root & reset dummy
            if(root == null){
                root = dummy.next;
                pre = dummy;
                dummy.next = null;
            }
        }
    }