populating-next-right-pointers-in-each-node

gistfile1.txt

/*
https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/

차분히 생각해보면(대부분의 BST 문제는 recursive로 푼다), left->right는 right!=NULL 체크로 쉽게 연결할 수 있는데
right->parent's sibling's left 연결이 헷갈릴 수 있다.

key는 현재 자신의 sibling이 존재하는지 node는 알수없기 때문에 parent에서 children의 sibling이 존재하는지를 체크해줘서 연결해줘야
한다는 것을 눈치 채는 것.

첫번째시도 : 문제의 조건인 You may only use constant extra space 을 깜빡하고 recursive로 작성
두번째시도 : BFS 연습도 할겸 BFS로 짬
세번째시도 : 문제 출제제가 의도하는대로 모든 node는 next point가 존재하므로 간단하게 while loop 두개로 짬

뭔가 좋은 문제는 아닌것 같다 왜냐하면 억지로 next, constant memory 제약을 줘서 next를 이용한 loop로 풀이를 강제하는 느낌.
*/

/**
 * 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) {}
 * };
 */
 
/* 
 //첫번째 풀이(recursive): 문제의 조건인 constant space에 위배됨.
class Solution {
    public:
    void connect(TreeLinkNode *root) {
       if(root != NULL) root->next = NULL;
       
       connectChild(root);
    }
    
    void connectChild(TreeLinkNode* node) {
        if(node == NULL) return;
        
        if(node->left != NULL) {
            node->left->next = node->right;
            
            connectChild(node->left);
        } 
         
        if(node->right != NULL) {
            if(node->next != NULL) node->right->next = node->next->left;
            else node->right->next = NULL;
            
            connectChild(node->right);
        } 
    }
};
*/

/*두번째 풀이(BFS): 문제의 조건인 constant space에 위배됨.
class Solution {
    public:
    void connect(TreeLinkNode *root) {
        if(root != NULL) root->next = NULL;
        else return;
       
        int cnt=1;
        queue<TreeLinkNode*> input;
        input.push(root);
        
        while(!input.empty()) {
            TreeLinkNode* node = input.front();
            input.pop();
            
            if(node->left != NULL) input.push(node->left);
            if(node->right != NULL) input.push(node->right);
            
            for(int i=0 ; i<cnt-1 ; i++) {
                node->next = input.front();
                input.pop();
                
                if(node->next->left != NULL) input.push(node->next->left);
                if(node->next->right != NULL) input.push(node->next->right);
                
                node->next->next = NULL;
                node = node->next;
            }
            
            cnt*=2; //1, 2, 4, 8, 16..because this is perfect binary tree
        }
    }
};
*/

//세번째 풀이: 출제자의 의도대로 constant space를 이용하여 해결 
class Solution {
    public:
    void connect(TreeLinkNode *root) {
        if(root == NULL) return;
     
        TreeLinkNode * cur = root;
        
        while(cur) {
            TreeLinkNode * temp = cur;
            
            while(cur) {
                if(cur->left != NULL) {
                    cur->left->next = cur->right;
                }
                
                if(cur->right != NULL) {
                    if(cur->next != NULL) {
                        cur->right->next = cur->next->left;     
                    } else {
                        cur->right->next = NULL;
                    }
                }
                
                cur = cur->next;
            }
            
            if(temp == NULL) break;
            cur = temp->left;
        }
    }
};