#leetcode#Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to  NULL .
Initially, all next pointers are set to  NULL .
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example, Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

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

이 문제는 어떻게 보면 매우 복잡하지만 사실은 BFS의 변체이다. level order traversal은 이전의 BFS를 바탕으로 next 바늘의 값 부여 조작을 추가했을 뿐이다.
모처럼 생각의 방향을 알아차렸는데, 문제를 많이 풀면 과연 고양이처럼 호랑이를 그릴 수 있구나...
여기에 또 하나의 실수를 저질렀다.queue를 썼다.현재 줄의 마지막 노드인지 아닌지를 판단하기 위해 int size =queue를 미리 사용했습니다.크기 () 이 길이를 저장하러 갔어요...

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null){
            return;
        }
        LinkedList<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeLinkNode curNode = queue.pop();
                // if(queue.size() == 0){   queue.size() 。。。  size
                if(i == size - 1){  //  i == size - 1 
                    curNode.next = null;
                }else{
                    curNode.next = queue.peek();
                }
                if(curNode.left != null){
                    queue.offer(curNode.left);
                }
                if(curNode.right != null){
                    queue.offer(curNode.right);
                }
            }
        }
    }
}

위의queue를 사용한 해법 공간의 복잡도는 O(n)이다. 사실 이 문제의 모든 줄의next바늘은 현재 줄의 결점을queue로 연결했다. 이 점을 잘 이용하면 몇 개의 바늘로 값을 왔다 갔다 하면 된다. lastHead는 현재 줄의 첫 번째 노드를 나타내고curHead는 다음 줄의 첫 번째 노드를 나타내고pre를 사용한다.next로 같은 줄의 앞뒤 결점을 연결합니다.
공간 복잡도 O(1)

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null){
            return;
        }
        
        TreeLinkNode lastHead = root;
        TreeLinkNode curHead = null;
        TreeLinkNode pre = null;
        
        while(lastHead != null){
            TreeLinkNode lastCur = lastHead;
            
            while(lastCur != null){
                if(lastCur.left != null){
                    if(curHead == null){
                        curHead = lastCur.left;
                        pre = curHead;
                    }else{
                        pre.next = lastCur.left;
                        pre = pre.next;
                    }
                }
                
                if(lastCur.right != null){
                    if(curHead == null){
                        curHead = lastCur.right;
                        pre = curHead;
                    }else{
                        pre.next = lastCur.right;
                        pre = pre.next;
                    }
                }
                
                lastCur = lastCur.next;
            }
            
            lastHead = curHead;
            curHead = null;
        }
    }
}