【LeetCode】116. 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.

Recursive approach is fine, implicit stack space does not count as extra space for this problem.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

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

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 (root==NULL) return;
        if(root->left) root->left->next=root->right;
        if(root->right) root->right->next=root->next?root->next->left:NULL;
        connect(root->left);
        connect(root->right);
    }
};

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;
        queue q;
        q.push(root);
        q.push(NULL);
        while(true){
            TreeLinkNode* cur=q.front();
            q.pop();
            if(cur){
                cur->next=q.front();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }else{
                if(q.size()==0||q.front()==NULL) return;
                q.push(NULL);
            }
            
        }
    }
};

3. 앞의 두 가지 방법은 공간 복잡도 O(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) {
        // O(1)
        if (!root) return;
        TreeLinkNode *start = root, *cur = NULL;
        while (start->left) {
            cur = start;
            while (cur) {
                cur->left->next = cur->right;
                if (cur->next) cur->right->next = cur->next->left;
                cur = cur->next;
            }
            start = start->left;
        }
    }
};

참조 링크