Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node

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) {
        
        // return connect1(root);
        
        return connect2(root);
    }
    
    Node* connect2(Node* root) {
        if (root == nullptr)
            return root;
        
        Node* value;
        queue<Node*> q;
        
        q.push(root);
        
        int size = 0;
        while (!q.empty()) {
            size = q.size();
            
            for (int i = 0; i < size; i++) {
                value = q.front();
                q.pop();
                
                if (i < size - 1)
                    value->next = q.front();
                
                if (value->left)
                    q.push(value->left);
                if (value->right)
                    q.push(value->right);
            }
        }
        
        return root;
    }
    
    Node* connect1(Node* root) {
        if (root == nullptr)
            return root;
        
        Node* leftmost = root;
        
        while(leftmost->left != nullptr) {
            Node* head = leftmost;
            
            while (head != nullptr) {
                head->left->next = head->right;
                
                if (head->next != nullptr) {
                    head->right->next = head->next->left;
                }
                
                head = head->next;
            }
            
            leftmost = leftmost->left;
        }
        
        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);
    }
    
    Node* helper(Node* root) {
        Node* value;
        Node* prevNode = nullptr;
        int idx = 0;
        queue<Node*> q;
        q.push(root);
        
        while(!q.empty()) {
            value = q.front();
            q.pop();
            if (prevNode != nullptr && prevNode->val != value->val)
                value->next = prevNode;
            
            if (value->left)
                q.push(value->left);
            if (value->right)
                q.push(value->right);
            
            prevNode = value->left;
        }
        
        return root;
    }
    
};

이러면 right child 만 안나온다

fail test case

Your input : [1,2,3,4,5,6,7]

Output : [1,#,2,#,4,6,#]

Expected : [1,#,2,3,#,4,5,6,7,#]

그래서 조금 고쳤는데

class Solution {
public:
    Node* connect(Node* root) {
        return helper(root);
    }
    
    Node* helper(Node* root) {
        Node* value;
        Node* valueTemp;
        Node* prevNode = nullptr;
        queue<Node*> qTemp;
        queue<Node*> q;
        q.push(root);
        qTemp.push(nullptr);
        
        while(!q.empty()) {
            value = q.front();
            q.pop();
            
            //if (prevNode != nullptr && prevNode->val != value->val)
            //    value->next = prevNode;
            
            if (value->left) {
                q.push(value->left);
                qTemp.push(value->left);
            }
            if (value->right) {
                q.push(value->right);
                qTemp.push(value->right);
                qTemp.push(nullptr);
            }
            
            // if (prevNode->val != value->val)
            //    prevNode = value->left;
            valueTemp = qTemp.front();
            qTemp.pop();
            value->next = valueTemp;
            if (valueTemp != nullptr && valueTemp->val == value->val) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
        }
        
        return root;
    }
    
};

Your input : [1,2,3,4,5,6,7]

Output : [1,#,2,3,#,4,5,#]

Expected : [1,#,2,3,#,4,5,6,7,#]

조금만 고쳐졌다..;

class Solution {
public:
    Node* connect(Node* root) {
        return helper(root);
    }
    
    Node* helper(Node* root) {
        Node* value;
        Node* valueTemp;
        // Node* prevNode = nullptr;
        queue<Node*> qTemp;
        queue<Node*> q;
        int level = 0;
        
        q.push(root);
        qTemp.push(nullptr);
        
        while(!q.empty()) {
            value = q.front();
            q.pop();
            
            //if (prevNode != nullptr && prevNode->val != value->val)
            //    value->next = prevNode;
            
            if (value->left) {
                q.push(value->left);
                qTemp.push(value->left);
            }
            if (value->right) {
                q.push(value->right);
                qTemp.push(value->right);
                qTemp.push(nullptr);
            }
            if (value->left || value->right)
                level++;
            
            // if (prevNode->val != value->val)
            //    prevNode = value->left;
            valueTemp = qTemp.front();
            qTemp.pop();
            value->next = valueTemp;
            if (valueTemp != nullptr && valueTemp->val == value->val) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
            
            if (value->next == nullptr) {
                level--;
            }
            
            if (value->next == nullptr && level > 1) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
            
            /*
            if (qTemp.size() > 1) {
                valueTemp = qTemp.front();
                qTemp.pop();
                value->next = valueTemp;
            }
            */
        }
        
        return root;
    }
    
};

현재 레벨을 가지고 어떻게 해보려고 했는데 항상 5 다음이 문제였다;

노드의 level 에 따라서 nullptr 을 만났을 때 면제권? 한 번 더 qTemp 의 다음으로 가리키도록 하는 것을 줘야겠다고 생각이 들었는데,

그러면 각 노드마다 자신의 level 을 기록해놔야하는데 더 쉬운 방법이 없을까 생각했었다. 시간 많이 지나서 걍 솔루션 고고

문제점

와 솔루션보고 그래도 생각하는 게 조금 는 게 느껴졌다? 

일단 처음 문제 보고 아 level order traversal 이구나 알아서 queue 를 써야겠네? 생각하고 -> 1학기에 자료구조를 들었으니까... 기억력;

전 노드를 저장해 놓고 그 다음 노드에서 그 전 노드를 저장하면 되는 거 아닌가? 생각하다가 

현재 노드에서 다음 노드를 저장해놓으면 되는 거 아닌가? 큐에 있을텐데.. 생각도 하고

level 을 사용하면 될 것 같은데? 근데 이러면 다시 다 저장해야되는 거 아니야? 생각했다

솔루션 보니까 두 가지 방법이 있었는데 하 생각했던 거 있어서 진짜 이렇게라도 조금이나마 나를 칭찬하면서 참고했다..

1) leftmost 를 두고 사용하며, 현재 노드에 연결시키는 방법

leftmost 노드를 저장해놓고, head를 두고, head 에서 

leftmost.left != nullptr 로 멈추는 조건을 걸어놓고 

2) level 을 가지고 하는 방법

level을 가지고 해야겠다는 생각은 했었는데 다시 다른 자료구조에 넣어서 해야되나 생각했었는데

현재 큐의 사이즈를 가지고 i < size - 1 이것으로 rightmost 한 노드를 제외하고 next 에 연결시킬 수 있었다.

아 진짜 풀 수 있었는데~~~~~~(못 풀었을테지만) ㅋㅋㅋㅋㅋㅋㅋㅋ 하면서 기쁜 마음으로 솔루션 보면서 소스 수정했다