Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 트리의 최소 깊이 구하기 — BFS 레벨 순회 완전 정복

문제 설명

하나의 이진 트리(binary tree)가 주어졌을 때, 해당 트리의 최소 깊이(minimum depth)를 구하는 것이 이 글의 목표입니다. 여기서 최소 깊이란 루트 노드에서 가장 가까운 리프(leaf) 노드까지의 최단 경로에 포함된 노드의 개수를 의미합니다.

예를 들어, 아래와 같은 이진 트리가 입력으로 주어진다고 가정해 보겠습니다.

C++로 이진 트리의 최소 깊이 구하기 — BFS 레벨 순회 완전 정복

루트 노드(3)에서 가장 가까운 리프 노드는 9이므로, 이 경우 출력 결과는 2가 됩니다.

접근 방법: BFS(너비 우선 탐색)

이 문제는 레벨 순회(level-order traversal), 즉 BFS 방식으로 효율적으로 해결할 수 있습니다. 트리를 위에서부터 한 층씩 내려가며 탐색하다가 처음으로 리프 노드를 만나는 순간의 레벨이 곧 최소 깊이이기 때문입니다. 구체적인 알고리즘 단계는 다음과 같습니다.

  1. 트리 노드를 저장할 배열 aa를 정의하고, 그 끝에 루트 노드를 삽입합니다.
  2. 다음 레벨의 노드를 저장할 또 다른 배열 ak를 정의하고, level = 0으로 초기화합니다.
  3. 루트가 null이라면 즉시 0을 반환합니다.
  4. aa의 크기가 0이 아닌 동안 아래 과정을 반복합니다.
    • ak를 비우고 level을 1 증가시킵니다.
    • aa에 있는 모든 노드 a에 대해 검사합니다.
      • a의 왼쪽 자식과 오른쪽 자식이 모두 존재하지 않으면, 현재 level 값을 반환하고 반복문을 빠져나옵니다.
      • 왼쪽 자식이 존재하면 ak의 끝에 추가합니다.
      • 오른쪽 자식이 존재하면 ak의 끝에 추가합니다.
    • aa = ak로 갱신하여 다음 레벨로 이동합니다.
  5. 반복이 모두 끝나면 0을 반환합니다.

C++ 구현 예제

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

#include <bits/stdc++.h>
using namespace std;
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:
    int minDepth(TreeNode* root) {
        vector<TreeNode*> aa;
        aa.push_back(root);
        vector<TreeNode*> ak;
        int level = 0;
        if (root == NULL || root->val == 0) {
            return 0;
        }
        while (aa.size() != 0) {
            ak.clear();
            level++;
            for (TreeNode* a : aa) {
                if ((a->left == NULL || a->left->val == 0) && (a->right == NULL || a->right->val == 0)) {
                    return level;
                    break;
                }
                if (a->left != NULL) {
                    ak.push_back(a->left);
                }
                if (a->right != NULL) {
                    ak.push_back(a->right);
                }
            }
            aa = ak;
        }
        return 0;
    }
};
main(){
    Solution ob;
    vector<int> v = {3,9,20,NULL,NULL,15,7};
    TreeNode *root = make_tree(v);
    cout << (ob.minDepth(root));
}

실행 결과 확인

입력

{3,9,20,NULL,NULL,15,7}

출력

2

동작 원리와 성능 분석

위 예제에서 트리는 {3,9,20,NULL,NULL,15,7}로 구성됩니다. 루트 3의 왼쪽 자식인 9는 리프 노드이므로, 첫 번째 레벨 검사에서 바로 최소 깊이 2가 반환됩니다. 만약 DFS(깊이 우선 탐색)를 사용했다면 전체 경로를 끝까지 확인한 후 최솟값을 비교해야 하지만, BFS는 가장 얕은 리프 노드를 먼저 발견하는 즉시 탐색을 종료할 수 있어 이 문제에 특히 적합합니다.

  • 시간 복잡도: O(N) — 최악의 경우 트리의 모든 노드를 한 번씩 방문합니다.
  • 공간 복잡도: O(N) — 레벨별 노드를 저장하는 큐(배열) 공간이 필요합니다.

이처럼 BFS 기반 레벨 순회를 활용하면 이진 트리의 최소 깊이를 간결하고 효율적으로 계산할 수 있습니다.