LeetCode OJ:Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

  
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example, Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

알고리즘 사상: 층차적으로 훑어보는 사상에 따라 각 층의 원소를 연결하고curLev 변수로 현재 층에 접근한 몇 번째 원소를 표시하며,nextLev는 다음 층의 몇 개의 원소를 표시하고 보조 구조체 지침으로 이 층의 노드를 연결한다.

/**
 * 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)return;
        queue<TreeLinkNode *>que;
        TreeLinkNode *p;
        p=NULL;
        int minLen=0;
		int curLev=1;
		int nextLev=0;
        que.push(root);
        while(!que.empty()){
            TreeLinkNode *cur=que.front();
            que.pop();
            if(p==NULL)p=cur;
            else {p->next=cur;p=cur;}
            if(cur->left){que.push(cur->left);nextLev++;}
            if(cur->right){que.push(cur->right);nextLev++;}
            if(--curLev==0){
				p->next=NULL;
                p=NULL;
				curLev=nextLev;
				nextLev=0;
			}
        }
    }
};

교체 버전 2:
시간 복잡도 O(n), 공간 복잡도 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) {
        while(root){
            TreeLinkNode *next=NULL;
            TreeLinkNode *prev=NULL;
            for(;root;root=root->next){
                if(!next)next=root->left?root->left:root->right;
                
                if(root->left){
                    if(prev)prev->next=root->left;
                    prev=root->left;
                }
                if(root->right){
                    if(prev)prev->next=root->right;
                    prev=root->right;
                }
            }
            root=next;
        }
    }
};

귀속판
시간 복잡도 O(n), 공간 복잡도 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) {
        if(NULL == root)return;
        
        TreeLinkNode dummy(-1);
        TreeLinkNode *cur=root,*prev=&dummy;
        for(;cur;cur=cur->next){
            if(cur->left){
                prev->next=cur->left;
                prev=prev->next;
            }
            if(cur->right){
                prev->next=cur->right;
                prev=prev->next;
            }
        }
        connect(dummy.next);
    }
};