[OJ.leetcode] populating-next-right-pointers-in-each-node

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;

        }

    }

};