각 노드가 정수 값을 가지는 이진 트리가 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 노드 값의 합이 주어진 목표 값과 같아지는 루트에서 리프까지의 경로를 모두 찾는 것입니다.
예를 들어 트리가 [5,4,8,11,null,13,4,7,2,null,null,5,1]과 같이 구성되어 있고, 목표 합(sum)이 22라면 다음 그림과 같습니다.
이때 조건을 만족하는 경로는 [[5,4,11,2],[5,8,4,5]] 두 가지입니다.
풀이 접근 방식: DFS(깊이 우선 탐색)
이 문제는 약간 변형된 DFS(깊이 우선 탐색) 함수를 사용하면 깔끔하게 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- DFS 함수는 현재 노드(root), 남은 목표 합(sum), 임시 경로 배열(temp) 세 가지를 인자로 받습니다.
- 현재 노드가 존재하지 않으면(null) 즉시 반환합니다.
- 현재 노드가 리프 노드(왼쪽·오른쪽 자식이 모두 없음)라면:
- 남은 sum이 현재 노드의 값과 같다면, 노드 값을 temp에 추가한 뒤 temp 전체를 결과(res)에 저장하고, 다시 마지막 원소를 제거합니다.
- 리프가 아니라면 현재 노드의 값을 temp에 추가합니다.
- 왼쪽 자식에 대해
dfs(left, sum - 노드값, temp)를 재귀 호출합니다. - 오른쪽 자식에 대해
dfs(right, sum - 노드값, temp)를 재귀 호출합니다. - 재귀 호출이 끝나면 temp에서 마지막 원소를 제거하여(백트래킹) 상위 경로를 복원합니다.
핵심 아이디어는 각 노드를 지날 때마다 목표 합에서 노드 값을 빼면서 내려가고, 리프에 도달했을 때 남은 값이 0(즉, sum == 노드 값)이면 그 경로를 정답으로 기록하는 것입니다. 재귀 호출 종료 후 temp에서 원소를 빼는 백트래킹 과정을 통해 다른 경로를 탐색할 수 있습니다.
C++ 구현 예제
아래 전체 코드를 통해 동작을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = 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 < vector <int> > res;
void dfs(TreeNode* root, int sum, vector <int>& temp){
if(!root)return;
if(!root->left && !root->right){
if(sum == root->val){
temp.push_back(root->val);
res.push_back(temp);
temp.pop_back();
}
return;
}
temp.push_back(root->val);
dfs(root->left, sum - root->val, temp);
dfs(root->right, sum - root->val, temp);
temp.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
res.clear();
vector <int> temp;
dfs(root, sum, temp);
return res;
}
};
main(){
Solution ob;
vector<int> v = {5,4,8,11,NULL,13,4,7,2,NULL,NULL,NULL,NULL,5,1};
TreeNode *root = make_tree(v);
print_vector(ob.pathSum(root, 22));
}입력
[5,4,8,11,null,13,4,7,2,null,null,5,1] 22
출력
[[5, 4, 11, 2],[5, 8, 4, 5]]
정리
이 풀이는 트리의 모든 루트-리프 경로를 한 번씩만 방문하므로, 시간 복잡도는 O(N)(N은 노드 수), 공간 복잡도는 경로를 저장하기 위한 O(H)(H는 트리의 높이) 수준입니다. 백트래킹을 활용한 DFS 패턴은 경로 탐색 문제뿐 아니라 조합(combination) 유형의 다양한 트리 문제에서도 널리 응용되므로, 동작 원리를 잘 익혀두면 좋습니다.