C++로 이진 트리 각 노드의 다음 오른쪽 포인터 채우기 II

문제 소개

각 노드가 (data, left, right, next) 네 가지 필드를 가지는 이진 트리가 있다고 가정해 보겠습니다. left 포인터는 왼쪽 서브트리를, right 포인터는 오른쪽 서브트리를 가리키며, next 포인터는 같은 레벨(깊이)에서 바로 오른쪽에 인접한 노드를 가리킵니다. 해당 위치에 더 이상 노드가 존재하지 않으면 next는 null이 됩니다.

처음에는 모든 next 포인터가 null로 초기화되어 있으며, 우리의 목표는 이 링크들을 올바르게 채워 넣는 것입니다. 예를 들어 아래와 같은 트리가 주어지면, 변환 후 각 노드의 next 포인터는 같은 깊이의 다음 노드를 가리키게 됩니다.

해결 접근 방법

이 문제는 큐(queue)와 같은 추가 자료구조 없이, 이미 연결된 상위 레벨의 next 포인터를 활용해 다음 레벨의 노드들을 순서대로 잇는 방식으로 해결할 수 있습니다. 완전 이진 트리가 아닌 일반적인 이진 트리에도 적용 가능하다는 점이 이번 버전(II)의 핵심 특징입니다.

알고리즘에서 사용하는 세 가지 핵심 변수는 다음과 같습니다.

pre: 현재 레벨에서 탐색 중인 노드
prev: 다음 레벨에서 가장 최근에 연결된 노드
nextPre: 다음 레벨 탐색의 시작점이 될 첫 번째 노드

전체 알고리즘 단계는 다음과 같습니다.

pre = root, nextPre = null, prev = null로 초기화합니다.
pre가 null이 아닌 동안 다음을 반복합니다.
- pre가 null이 아닌 동안:
  - pre의 왼쪽 자식이 존재하면: prev가 null이 아니면 prev->next = pre->left로 연결하고, null이면 nextPre = pre->left로 시작점을 지정합니다. 이후 prev = pre->left.
  - pre의 오른쪽 자식이 존재하면: prev가 null이 아니면 prev->next = pre->right로 연결하고, null이면 nextPre = pre->right로 시작점을 지정합니다. 이후 prev = pre->right.
  - pre = pre->next로 현재 레벨의 다음 노드로 이동합니다.
- pre = nextPre로 다음 레벨의 시작 노드로 이동합니다.
- nextPre와 prev를 다시 null로 초기화합니다.
모든 연결이 완료되면 root를 반환합니다.

C++ 구현 예제

아래 구현 코드를 통해 동작 방식을 더 명확하게 이해할 수 있습니다.

#include <bits/stdc++.h>
#include <stack>
using namespace std;
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): val(_val), left(_left), right(_right), next(NULL) {}
};
class Solution {
    public:
    Node* connect(Node* root) {
        Node* pre = root;
        Node* nextPre = NULL;
        Node* prev = NULL;
        while(pre){
            while(pre){
                //cout << pre->val << endl;
                if(pre->left){
                    if(prev){
                        prev->next = pre->left;
                    }else{
                        nextPre = pre->left;
                    }
                    prev = pre->left;
                }
                if(pre->right){
                    if(prev){
                        prev->next = pre->right;
                    }else{
                        nextPre = pre->right;
                    }
                    prev = pre->right;
                }
                pre = pre->next;
            }
            //cout << "*" << endl;
            pre = nextPre;
            nextPre = NULL;
            prev = NULL;
        }
        return root;
    }
};
void printTree(Node* root) {
    cout << "[";
    if (root == NULL) return;
    queue<Node*> q;
    Node *curr;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        curr = q.front();
        q.pop();
        if (curr == NULL){
            q.push(NULL);
        } else {
            if(curr->left)
                q.push(curr->left);
            if(curr->right)
                q.push(curr->right);
            if(curr->val == 0){
                cout << "null" << ", ";
            } else {
                cout << curr->val << ", ";
                if (curr->next == NULL) cout<<"#, ";
            }
        }
    }
    cout << "]"<<endl;
}
int main() {
    Node* root;
    Node nodeFour(4);
    Node nodeFive(5);
    Node nodeSeven(7);
    Node nodeTwo(2,&nodeFour,&nodeFive);
    Node nodeThree(3,NULL,&nodeSeven);
    Node nodeOne(1,&nodeTwo,&nodeThree);
    root = &nodeOne;
    Solution ob;
    root = ob.connect(root);
    printTree(root);
}

실행 결과 확인

입력

[1,2,3,4,5,null,7]
Node* root;
Node nodeFour(4);
Node nodeFive(5);
Node nodeSeven(7);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,NULL,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;

출력

[1, #, 2, 3, #, 4, 5, 7, #]

출력에서 #는 해당 레벨의 끝을 의미합니다. 즉, 루트 1의 next는 없고(#), 2의 next는 3, 4의 next는 5이며, 7의 next는 없음(#)을 나타냅니다.

복잡도 분석

시간 복잡도: O(n) — 각 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(1) — 큐나 재귀 호출 없이 포인터 변수 몇 개만 사용하므로 추가 공간이 상수입니다.