Populating Next Right Pointers in Each Node II

117. Populating Next Right Pointers in Each Node II

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

Populating Next Right Pointers in Each Node II - LeetCode

Language: C++

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (root)
            return helper2(root);
        else
            return nullptr;
    }
    
    Node* helper2(Node* root) {
        queue<Node *> q;
        q.push(root);
        int size = 0;
        while(!q.empty()) {
            size = q.size();
            for(int i = 0; i < size; i++) {
                
                Node* node = q.front();
                q.pop();
                
                if (i < size - 1) {
                    node->next = q.front();
                }
                
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
        }
        
        return root;
    }
};

void solve(Node *root){
        if(!root) return;
        Node *temp=root, *curr, *post;
        while(temp){
            if(temp->left){
                post=temp->right, curr=temp->next;
                while(curr){
                    if(post) break;
                    if(post=curr->left) break;
                    if(post=curr->right) break;
                    curr = curr->next;
                }
                temp->left->next = post;
            }
            if(temp->right){
                post=NULL, curr=temp->next;
                while(curr){
                    if(post=curr->left) break;
                    if(post=curr->right) break;
                    curr = curr->next;
                }
                temp->right->next = post;
            }
            temp = temp->next;
        }
        solve(root->left);
        solve(root->right);
    }
    
    Node* connect(Node *root) {
        solve(root);
        return root;
    }

이거는 멋있는 코드1

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) {
            return NULL;
        }
        queue<Node*> q;
        q.push(root);
        Node* lastNode = root;
        while(!q.empty()) {
            Node * tmp = q.front();
            q.pop();
            if(tmp -> left) q.push(tmp -> left);
            if(tmp -> right) q.push(tmp -> right);
            if(tmp == lastNode) {
                tmp -> next = NULL;
                lastNode = q.back();
            } else {
                tmp -> next = q.front();
            }
        }
        return root;
    }
};

이거는 멋있는 코드2

class Solution {
public:
    Node* findNext(Node* root){
        while(root){
            if(root -> left)
                return root -> left;
            if(root -> right)
                return root -> right;
            root = root -> next;
        }
        return NULL;
    }
    Node* connect(Node* root) {
        Node* p = root;
        while(p){
            Node* q = p;
            while(p){
                if(p -> left){
                    if(p -> right){
                        p -> left -> next = p -> right;
                    }
                    else
                        p -> left -> next = findNext(p -> next);
                }
                if(p -> right){
                    p -> right -> next = findNext(p -> next);
                }
                p = p -> next;
            }
            if(q -> left)
                p = q -> left;
            else if(q -> right)
                p = q -> right;
            else
                p = findNext(q -> next);
        }
        return root;
    }
};

시도

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        // return helper(root);
        
        if (root)
            return helper2(root);
        else
            return nullptr;
    }
    
    Node* helper2(Node* root) {
        queue<Node *> q;
        q.push(root);
        int size = 0;
        while(!q.empty()) {
            size = q.size();
            for(int i = 0; i < size; i++) {
                
                Node* node = q.front();
                q.pop();
                
                if (i < size - 1) {
                    node->next = q.front();
                    /*
                    if (node->left) {
                        if (node->right)
                            node->left->next = node->right;
                        else {
                            Node* node2 = node->next;
                            while (node2) {
                                if (node2->left) {
                                    node->left->next = node2->left;
                                    break;
                                }
                                else if (node2->right) {
                                    node->left->next = node2->right;
                                    break;
                                }
                                node2 = node2->next;
                            }
                        }
                    }*/
                }
                
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
                
            }
        }
        
        return root;
    }
    
    Node* helper(Node* root) {
        Node* leftmost = root;
        
        while(leftmost->left) {
            
            Node* head = leftmost;
            
            while (head) {
                
                if (head->left)
                head->left->next = head->right;
                
                if (head->next) {
                    if (head->next->left)
                        head->right = head->next->left;
                    else
                        head->right = head->next->right;
                }
                    
                head = head->next;
            }
            
            leftmost = leftmost->left;
        }
        
        return root;
    }
};

문제점

큐에 넣은 대로 하면 된다고 생각이 들어서 그건 뛰어넘고 leftmost 방법으로 도전해보려고 했으나

내 머릿속에서는 되는데 실제로는 안되었다.

그래서 큐에 넣는 방법으로 했으나 그것도 어설프게 했어서 실패하고.

어제 어렴풋이 생각했던 방법들을 솔루션으로 보게 되어 잘 익혔다고 생각했으나 다시 코드를 짜보니 제대로 안했나보다;

첫번째 코드가 큐에 넣는 방법(Populating Next Right Pointers in Each Node) 과 동일하고 

두번째 코드가 다른 방법인데 recursive 로 호출하고 left, right 의 null 여부에 따라서 node->next 를 반복하기도 한다.

집가서 밥먹고 잘란다 오늘 북한산 둘레길 갔더니 너무 잠오고 힘들다;;