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

[문제 풀이 사고방식]
두 갈래 나무에 대해 층차 역행을 사용하고 층차 역행 과정은 두 개queue를 사용하여 층을 나눈다

 1 /**
 2  * Definition for binary tree with next pointer.
 3  * public class TreeLinkNode {
 4  *     int val;
 5  *     TreeLinkNode left, right, next;
 6  *     TreeLinkNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public void connect(TreeLinkNode root) {
11         // Start typing your Java solution below
12         // DO NOT write main() function
13         if(root == null){
14             return;
15         }
16         
17         levelOrderTraverse(root);
18     }
19     
20     public void levelOrderTraverse(TreeLinkNode node){
21         LinkedList<TreeLinkNode> first = new LinkedList<TreeLinkNode>();
22         LinkedList<TreeLinkNode> second = new LinkedList<TreeLinkNode>();
23         first.add(node);
24         while(!first.isEmpty()){
25             TreeLinkNode tmp = first.poll();
26             if(tmp.left != null){
27                 second.add(tmp.left);
28             }
29             if(tmp.right != null){
30                 second.add(tmp.right);
31             }
32             if(first.isEmpty()){
33                 tmp.next = null;
34                 first.addAll(second);
35                 second.clear();
36             } else {
37                 tmp.next = first.peek();
38             }
39         }
40     }
41 }

 updated
제목에서constantspace만 사용할 수 있도록 요구하기 때문에, 위에서 두 개의queue를 사용하는 것은 옳지 않습니다.

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

이 문제의 주요 난점은 노드 5의next를 처리하는 데 있다. 왜냐하면 5의next는sibling을 가리키기 때문이다. 그러나 5층에서는 3의 인용을 얻을 수 없기 때문이다.
해결 방법은 2가 있는 층에 넥스트 링크가 만들어졌기 때문에 2만 있으면 3의 인용을 얻을 수 있고 이어서 3의 left 노드를 얻을 수 있다

 1 public void connect(TreeLinkNode root) {
 2         // Start typing your Java solution below
 3         // DO NOT write main() function
 4         if(root == null){
 5             return;
 6         }
 7         if(root.left != null){
 8             root.left.next = root.right;
 9         }
10         if(root.right != null){
11             root.right.next = (root.next != null) ? root.next.left : null;
12         }
13         
14         connect(root.left);
15         connect(root.right);
16     }