[LeetCode] 116. Populating Next Right Pointers in Each Node c++

문제

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

 

next pointer 를 next right node를 가르키도록 다음 포인터를 채웁니다.

next right node가 없으면 null pointer로 설정합니다.

문제 해결

Node* connect(Node* root) {
       //base case
    if (root == NULL) return NULL;
   	 //connects the left subtree of same level with right subtree of that same level 
    if (root->left != NULL) {
        root->left->next = root->right;
    }
      //connect the rightmost node of a level to the leftmost node of the next level.
    if (root->right != NULL && root->next != NULL) {
        root->right->next = root->next->left;
    }
      //recursive calls for left and right subtrees.
    connect(root->left);
    connect(root->right);
    return root;
}

 

다른 풀이

class Solution {
public:
    Node* connect(Node* root) {
        
        Node *prev = root, * curr;
        while(prev){
            curr = prev;
            while(curr && curr->left){
                curr->left->next = curr->right;
                if(curr->next){
                    curr->right->next = curr->next->left;
                }
                curr = curr->next;
            }
            prev = prev->left;
        }
        return root;
    }
};