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

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

Populating Next Right Pointers in Each Node - LeetCode

Populating Next Right Pointers in Each Node - Medium

 

완전한 이진탐색트리가 주어졌을때, 노드들에 next라는 포인터 성분이 추가된다.

이 next 포인터가 완전이진탐색트리에서 바로 오른쪽에 있는 노드를 가리키게 되고, 가장 오른쪽 노드는 NULL을 가리키게 되도록 만드는 문제다.

 

queue를 이용하여 BFS로 노드를 훑자.

이 때, 가장 오른쪽 노드를 훑게 되는 순서를 보게 되면

1,3,7,15, ... 로 이진법으로 나타내면 1, 11, 111, 1111, ... 이 된다. 이를 이용하자.

 

전체 풀이 코드

class Solution {
public:
    queue<Node*> q;
    Node* connect(Node* root) {
        int n1 = 0, n2 = 1;
        if (root) q.push(root);
        while (!q.empty()) {
            Node* node = q.front();
            q.pop();
            n1++;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            if (n1==n2) node->next = NULL, n2=(n2<<1)^1;
            else {
                Node* next = q.front();
                node->next = next;
            }
        }
        return root;
    }
};