각 노드의 Populating Next Right Pointers - 각 노드에 next right 포인터를 채웁니다.

원제:
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 .
=> 모든 노드의 넥스트 바늘을 오른쪽의 노드를 가리키고 오른쪽에 노드가 없으면null을 가리킨다
Initially, all next pointers are set to NULL .
=> 모든next 노드는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).

=>완벽한 두 갈래 나무라고 가정한다(모든 잎은 한 level에 있고 모든 부자 나무는 두 개의 노드가 있다)

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

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:

    void connect(TreeLinkNode *root) {
    }
};
  
 
효동 분석:
먼저 생각나는 것은 두 갈래 나무의 범람이다. 먼저 범람한 왼쪽 나무를 오른쪽 나무로 가리키면 다음과 같은 삼각형을 구성할 수 있다. 그 중에서null은 초기화된 값이다.(5도null을 가리키며 그려지지 않음)
            1  -> null       /        \      2  ->    3 ->null     /\         /\   4->5     6->7->null 
다음 단계는 5와 6 사이를 연결하는 것이다. 이것이 바로 오른쪽 나무의next가 자신의next를 가리키는 왼쪽 나무이다.이렇게 하면 얻을 수 있다
    1 -> NULL       / \      2 -> 3 -> NULL     /\ /\    4->5->6->7 -> NULL 
다음은 여러 가지 반복적인 알고리즘 선택이다.먼저 차례차례 훑어보기를 선택했습니다.http://blog.csdn.net/u011960402/article/details/14517135안에 상세한 묘사가 있다.그래서 다음 코드가 생겼어요.
코드 구현:
실현 1: 귀속
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:

    void connect(TreeLinkNode *root) {
        if (NULL == root) {
            return;
        }

        TreeLinkNode *left = root->left;
        TreeLinkNode *right = root->right;

        /* set the next pointer for his left child */
        if (NULL != left) {
            left->next = right;
        }

        /* set the next pointer for his right child */
        if (NULL != right && NULL != root->next) {
            right->next = root->next->left;
        }

        /* do it recursively */
        connect(left);
        connect(right);

    }
};
  
실행 결과:
14/14 test cases passed. 
Status:  
Accepted
   
Runtime: 
52 ms 
구현 2:
비귀속 실현:
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root == NULL) return;
        stack<TreeLinkNode*> TreeStack;

        while(root || !TreeStack.empty()){
            while(root){
                TreeStack.push(root);
                if(root->left){
                    root->left->next = root->right;
                    if(root->next)
                        root->right->next = root->next->left;
                }
                root = root->left;
            }
            root = TreeStack.top();
            TreeStack.pop();
            root = root->right;
        }

    }
};
  
실행 결과:
14/14 test cases passed. 
Status:  
Accepted
   
Runtime: 
104 ms 
이상하게도 시비귀속은 오히려 귀속 알고리즘보다 느리고 이상하다.
더 좋은 알고리즘을 제시해 주시면 감사합니다.