C++로 이진 트리의 경계 값 구하기 (반시계 방향 순회)

이진 트리 경계(Boundary) 문제란?

이진 트리가 하나 주어졌을 때, 루트에서 시작하여 반시계 방향으로 트리의 경계에 있는 노드 값들을 순서대로 구해야 합니다. 여기서 경계(boundary)는 중복 노드 없이 다음 세 부분을 포함합니다.

왼쪽 경계: 루트에서 가장 왼쪽 노드까지 내려가는 경로
잎 노드(Leaf): 자식이 없는 말단 노드들
오른쪽 경계: 루트에서 가장 오른쪽 노드까지 내려가는 경로 (역순으로 추가)

만약 루트에 왼쪽 서브트리나 오른쪽 서브트리가 존재하지 않는다면, 루트 자체가 해당 방향의 경계가 됩니다.

예를 들어 아래와 같은 이진 트리가 입력으로 주어지면,

C++로 이진 트리의 경계 값 구하기 (반시계 방향 순회)

출력은 반시계 방향 경계 순서인 [1, 2, 4, 7, 8, 9, 10, 6, 3]이 됩니다.

해결 접근 방법

문제는 크게 세 개의 보조 함수로 나누어 해결할 수 있습니다.

경계 값을 저장할 배열 ret을 정의합니다.
leftBoundary() 함수를 정의합니다. 노드가 null이거나 리프 노드라면 즉시 반환합니다. 그렇지 않으면 노드 값을 ret에 추가하고, 왼쪽 자식이 존재하면 왼쪽 자식에 대해 재귀 호출하며, 없다면 오른쪽 자식에 대해 호출합니다.
rightBoundary() 함수를 정의합니다. 노드가 null이거나 리프 노드라면 즉시 반환합니다. 오른쪽 자식이 존재하면 오른쪽 자식에 대해, 없으면 왼쪽 자식에 대해 먼저 재귀 호출한 뒤, 마지막에 노드 값을 ret에 추가합니다. 이렇게 하면 오른쪽 경계가 아래에서 위로(역순) 저장되어 반시계 방향 순서가 유지됩니다.
leaves() 함수를 정의합니다. 노드가 null이면 반환하고, 리프 노드라면 값을 ret에 추가합니다. 이후 왼쪽 자식과 오른쪽 자식을 각각 재귀적으로 순회합니다.
메인 로직에서는 다음과 같이 진행합니다.
- ret 배열을 초기화합니다.
- 루트가 존재하지 않으면 빈 배열을 반환합니다.
- 루트 값을 ret에 추가합니다.
- leftBoundary(루트의 왼쪽), leaves(루트의 왼쪽), leaves(루트의 오른쪽), rightBoundary(루트의 오른쪽) 순서로 호출합니다.
- ret을 반환합니다.

각 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(N)이며, 재귀 호출 깊이는 트리의 높이에 비례하므로 공간 복잡도는 O(H)입니다.

예제 코드

아래 C++ 구현을 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class TreeNode{
    public:
        int val;
        TreeNode *left, *right;
        TreeNode(int data){
            val = data;
            left = NULL;
            right = NULL;
        }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
public:
    vector<int> ret;
    void leftBoundary(TreeNode* node){
        if (!node || node->val == 0 || (!node->left && !node->right))
            return;
        ret.push_back(node->val);
        if (node->left && node->left->val != 0)
            leftBoundary(node->left);
        else
            leftBoundary(node->right);
    }
    void rightBoundary(TreeNode* node){
        if (!node || node->val == 0 || (!node->left && !node->right))
            return;
        if (node->right && node->right->val != 0) {
            rightBoundary(node->right);
        }
        else {
            rightBoundary(node->left);
        }
        ret.push_back(node->val);
    }
    void leaves(TreeNode* node){
        if (!node || node->val == 0)
            return;
        if (!node->left && !node->right) {
            ret.push_back(node->val);
        }
        leaves(node->left);
        leaves(node->right);
    }
    vector<int> boundaryOfBinaryTree(TreeNode* root){
        ret.clear();
        if (!root)
            return ret;
        ret.push_back(root->val);
        leftBoundary(root->left);
        leaves(root->left);
        leaves(root->right);
        rightBoundary(root->right);
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10};
    TreeNode *root = make_tree(v);
    print_vector(ob.boundaryOfBinaryTree(root));
}

입력

{1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10}

출력

[1, 2, 4, 7, 8, 9, 10, 6, 3]