Populating Next Right Pointers in Each Node 두 갈래 트리의next 노드 설정

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

제목 요구는 두 갈래 나무입니다. 각 노드는 세 개의 지침 요소를 포함하고 각 노드는 왼쪽 트리와 오른쪽 트리를 제외하고 같은 차원의 인접한 오른쪽 노드를 가리킵니다.
같은 단계의 오른쪽에 노드가 없으면,next를 비어 있고, 그렇지 않으면next를 오른쪽에 인접한 노드로 설정합니다.
해결 방법:
한 번에 모든 노드를 훑어보고 좌우 트리가 비어 있지 않으면 왼쪽 트리의next를 오른쪽 트리로 가리키고 이 노드의next가 비어 있으면 오른쪽 트리의next를 비어 있도록 설정합니다 (그림 분석 참조)
이 노드의next가 비어 있지 않으면 이 노드와 같은 차원에서 인접한 오른쪽 노드를 가리키는 왼쪽 트리 (그림 분석 참조)
여기에 하나의 대기열을 사용하여 루트 노드를 먼저 대기열에 넣고 대기열에서 노드 node를 꺼내고 node는 대기열을 제거하며 node 서브트리의next 노드 처리는 상기 분석에 따라 처리합니다.
코드는 다음과 같습니다.

 1 /**
 2  * Definition for binary tree with next pointer.
 3  * struct TreeLinkNode {
 4  *  int val;
 5  *  TreeLinkNode *left, *right, *next;
 6  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     void connect(TreeLinkNode *root) {
12         if(root == NULL)    return;
13         queue<TreeLinkNode *> q;
14         
15         root->next = NULL;
16         
17         q.push(root);
18         
19         while(!q.empty()){
20             TreeLinkNode *node = q.front();
21             q.pop();
22             
23             if(node->left != NULL && node->right != NULL){
24                 q.push(node->left);
25                 q.push(node->right);
26                 
27                 node->left->next = node->right;
28                 if(node->next == NULL)
29                     node->right->next = NULL;
30                 else{
31                     TreeLinkNode *node_next = q.front();
32                     node->right->next = node_next->left;
33                 }
34                 
35             }
36             
37         }
38         
39     }
40 };