이진 트리가 하나 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 트리에서 가장 깊은 위치에 있는 잎(리프) 노드들의 값의 합입니다.
예를 들어 아래와 같은 트리가 있다고 합시다.
이 경우 출력 결과는 15가 됩니다.
문제 해결 접근 방법
이 문제는 DFS(깊이 우선 탐색) 방식의 재귀 함수를 활용하면 간단하게 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- 레벨별 노드 값의 합을 저장할 맵(map) m과 최대 깊이를 나타내는 maxDepth 변수를 정의합니다.
- 노드와 레벨을 매개변수로 받는 재귀 함수 solve()를 정의합니다. 초기 레벨은 0으로 설정합니다.
- 노드가 존재하지 않으면(null) 즉시 함수를 종료합니다.
- maxDepth를 현재 레벨과 기존 maxDepth 중 더 큰 값으로 갱신합니다.
- m[level]에 현재 노드의 값을 누적하여 더합니다.
- 왼쪽 자식 노드에 대해 solve(left, level + 1)을 재귀 호출합니다.
- 오른쪽 자식 노드에 대해 solve(right, level + 1)을 재귀 호출합니다.
- 메인 함수에서는 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;
}
};
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 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);
//cout << maxDepth << endl;
return m[maxDepth];
}
};
main(){
vector<int> v = {1,2,3,4,5,NULL,6,7,NULL,NULL,NULL,NULL,8};
TreeNode *root = make_tree(v);
Solution ob;
cout << (ob.deepestLeavesSum(root));
}
입력
[1,2,3,4,5,null,6,7,null,null,null,null,8]
출력
15
동작 원리 정리
위 코드는 트리를 순회하면서 각 노드가 속한 레벨(깊이)을 기준으로 노드 값을 누적합니다. 순회가 모두 끝나면 maxDepth에는 트리의 최대 깊이가 저장되어 있으므로, 해당 레벨에 누적된 합계가 곧 가장 깊은 리프 노드들의 합이 됩니다. 이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다(n은 노드의 개수).