# 0117. Populating Next Right Pointers in Each Node II
###### tags: `Leetcode` `Medium` `BFS`
## 思路
### 思路一 O(N) O(N)
做BFS层序遍历但是先拿右边的node再拿左边的，这样每次拿到左边的node就会知道它的next是什么，因为会先查看右边的node，再查看左边的
当然也可以正常做BFS，这样每次拿到一个node，它的下一个就是queue.peek（）
### 思路二 O(N) O(1)
之前之所以需要用queue存，是因为对于每一层的任一个node来说，我们都无从知道它的下一个node在哪
但是由于这题会把每一层的node连起来，所以通过root，我们就可以把root的下一层连起来，以此类推，我们可以通过遍历已经连好next的一层node（也就是下面code里面的curr），来把下一层连接起来
当我们发现curr已经是null了，那么就需要进入到下一层，因此我们每次操作的时候都需要记录每一层最左边的node (Node leftMost)

## Code
### 思路一

class Solution {
    public Node connect(Node root) {
        Queue<Node> q = new LinkedList<>();
        if(root == null) return null;
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            Node prev = null;
            for(int i = 0;i < size;i++){
                Node curr = q.poll();
                if(i == 0){
                    curr.next = null;
                }
                else{
                    curr.next = prev;
                }
                prev = curr;
                if(curr.right!=null) q.add(curr.right);
                if(curr.left!=null) q.add(curr.left);
            }
        }
        return root;
    }
}

### 思路二

class Solution {
    Node leftMost;
    Node prev;
    public void processChild(Node childNode){
        if(leftMost==null){
            leftMost = childNode;
        }
        if(prev!=null){
            prev.next = childNode;
        }
        prev = childNode;
    }
    public Node connect(Node root) {
        if(root == null) return null;
        leftMost = root;
        Node curr;
        while(leftMost!=null){
            prev = null;
            curr = leftMost;
            leftMost = null;
            while(curr!=null){
                if(curr.left!=null)processChild(curr.left);
                if(curr.right!=null)processChild(curr.right);
                
                curr = curr.next;
            }
            
        }
        return root;
    }
}