C++로 이진 트리의 가장 깊은 리프 노드 값의 합 구하기

이진 트리가 주어졌을 때, 가장 깊은 곳에 위치한 리프(잎) 노드들의 값을 모두 더한 합계를 구하는 문제를 살펴보겠습니다.

예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.

이 트리에서 가장 깊은 리프 노드들은 레벨 3에 있는 7과 4입니다. 따라서 이 두 노드의 값을 더한 결과인 11이 출력됩니다.

문제 해결 접근 방법

이 문제는 재귀적으로 트리를 순회하면서 각 레벨별 노드 값의 합을 기록하는 방식으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

레벨별 합계를 저장할 맵(map) m과 최대 깊이를 나타내는 변수 maxDepth를 정의합니다.
노드와 레벨을 매개변수로 받는 재귀 함수 solve()를 정의합니다. 초기 레벨은 0으로 시작합니다.
현재 노드가 존재하지 않으면(null) 함수를 종료하고 반환합니다.
maxDepth를 현재 레벨과 기존 maxDepth 중 더 큰 값으로 갱신합니다.
맵의 해당 레벨 키에 현재 노드의 값을 누적합니다. 즉, m[level] += node->val
왼쪽 자식 노드와 오른쪽 자식 노드에 대해 각각 레벨을 1 증가시키며 solve()를 재귀 호출합니다.
메인 메서드에서는 maxDepth를 0으로 초기화한 후 solve(root, 0)을 호출하여 순회를 시작합니다.
최종적으로 m[maxDepth], 즉 가장 깊은 레벨의 노드 값 합계를 반환합니다.

아래 예제 코드를 통해 실제 구현 방법을 자세히 확인해 보겠습니다.

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;
    }
};
class Solution {
    public:
    int maxDepth;
    map <int, int> m;
    void solve(TreeNode* node, int level = 0){
        if(!node)return;
        maxDepth = max(level, maxDepth);
        m[level] += node->val;
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    int deepestLeavesSum(TreeNode* root) {
        maxDepth = 0;
        m.clear();
        solve(root);
        return m[maxDepth];
    }
};
main(){
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->right->right->right = new TreeNode(4);
    root->left->left->left = new TreeNode(7);
    Solution ob;
    cout << (ob.deepestLeavesSum(root));
}

입력

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(6);
root->right->right->right = new TreeNode(4);
root->left->left->left = new TreeNode(7);

출력

코드 설명

위 코드에서 Solution 클래스의 deepestLeavesSum() 메서드가 핵심 로직을 담당합니다. 트리 전체를 깊이 우선 방식으로 순회하면서 각 노드가 속한 레벨별로 값을 맵에 누적합니다. 순회가 끝나면 maxDepth에는 트리의 최대 깊이가 저장되어 있으므로, 해당 레벨에 누적된 합계를 그대로 반환하면 됩니다.

이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)이며, 여기서 n은 노드의 개수입니다. 공간 복잡도 역시 재귀 호출 스택과 맵 저장 공간 때문에 최악의 경우 O(n)이 됩니다.