C++로 이진 트리 각 레벨(행)의 최댓값 찾기

문제 개요

이진 트리가 주어졌을 때, 트리의 각 레벨(행)마다 가장 큰 값을 찾아야 합니다. 예를 들어 아래와 같은 이진 트리가 있다고 가정해 보겠습니다.

루트부터 마지막 레벨까지 순서대로 각 행의 최댓값만 모으면 결과 배열을 얻을 수 있습니다.

접근 방법 (DFS 재귀 활용)

이 문제는 깊이 우선 탐색(DFS)과 재귀 함수를 이용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 노드가 속한 레벨 번호를 추적하면서, 해당 레벨을 처음 방문했는지 여부에 따라 처리 방식을 나누는 것입니다.

결과를 저장할 배열 ans를 선언합니다.
트리 노드와 레벨(초깃값 0)을 인자로 받는 재귀 함수 solve()를 정의합니다.
현재 노드가 null이면 즉시 반환합니다.
현재 레벨이 ans의 크기와 같다면, 해당 레벨을 처음 방문한 것이므로 노드 값을 ans에 추가합니다.
그렇지 않다면 이미 방문한 레벨이므로, ans[level]과 현재 노드 값 중 더 큰 값으로 갱신합니다.
왼쪽 자식과 오른쪽 자식에 대해 각각 solve()를 호출하며 레벨을 1씩 증가시킵니다.
메인 함수에서는 루트 노드와 레벨 0으로 solve()를 호출한 뒤 ans를 반환합니다.

이 방식은 트리를 한 번만 순회하므로 시간 복잡도는 O(N), 공간 복잡도는 O(H)(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> ans;
    void solve(TreeNode* node, int level = 0){
        if(!node)return;
        if(level == ans.size()){
            ans.push_back(node->val);
        } else {
            ans[level] = max(ans[level], node->val);
        }
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    vector<int> largestValues(TreeNode* root) {
        solve(root);
        return ans;
    }
};
main(){
    vector<int> v = {1,3,2,5,3,NULL,9};
    TreeNode *tree = make_tree(v);
    Solution ob;
    print_vector(ob.largestValues(tree));
}

실행 결과

예제 입력으로 트리 [1,3,2,5,3,null,9]를 사용했습니다. 이 트리는 레벨 0에 1, 레벨 1에 3과 2, 레벨 2에 5, 3, 9가 배치되어 있으므로 각 레벨의 최댓값은 다음과 같습니다.

입력:

[1,3,2,5,3,null,9]

출력:

[1, 3, 9]

정리

레벨 정보를 재귀 호출과 함께 전달하면 BFS(큐) 없이도 DFS만으로 각 행의 최댓값을 손쉽게 구할 수 있습니다. 처음 도달한 레벨인지 판별하는 조건(level == ans.size()) 하나만 기억하면, 비슷한 유형의 '레벨별 통계' 문제(최솟값, 평균 등)에도 동일한 패턴을 응용할 수 있습니다.