Leetcode - 116. Populating Next Right Pointers in Each Node

문제

완전이진트리가 주어진다. 각 노드의 next 포인터에 같은 레벨에 있는 우측 노드를 연결해라.(가장 오른쪽 노드의 next 는 NULL)

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

Explanation: Given the above perfect binary tree (Figure A), your function should 
populate each next pointer to point to its next right node, just like in Figure B. 
The serialized output is in level order as connected by the next pointers, 
with '#' signifying the end of each level.

해결

기본적으로 tree를 BFS순회. 단 right, left 자식 순서로 queue에 넣는다. 그리고 level이 바뀌면 null부터 시작해서 순차적으로 노드를 등록. 아래 BFS코드는 템플릿처럼 외울것!

class Solution {
public:
    Node* connect(Node* root) {
        if (!root)
            return root;
        queue<pair<Node *, int>> q;
        Node *prev = NULL;
        int prev_level = 0;
        
        root->next = NULL;
        q.push(make_pair(root, 0));
        while (!q.empty()) {
            pair<Node *, int> check = q.front();
            q.pop();
            Node *node = check.first;
            int level = check.second;
            if (prev_level != level) {
                prev = NULL;
                prev_level = level;
            }
            node->next = prev;
            prev = node;
            
            if (node->right)
                q.push(make_pair(node->right, level + 1));
            if (node->left)
                q.push(make_pair(node->left, level + 1));
            
        }
        return root;
    }
};