문제 개요
이진 트리가 하나 주어졌을 때, 트리에 있는 모든 오른쪽 잎(right leaf) 노드 값의 합을 구하는 문제입니다. 여기서 오른쪽 잎이란 부모 노드의 오른쪽 자식이면서 동시에 자기 자신은 자식이 없는 노드를 의미합니다.
예를 들어 아래와 같은 이진 트리가 입력으로 주어진다고 가정해 보겠습니다.
이때 출력은 17입니다. 이 트리에는 값이 각각 7과 10인 두 개의 오른쪽 잎 노드가 존재하고, 7 + 10 = 17이 되기 때문입니다.
풀이 접근 방법
이 문제는 DFS(깊이 우선 탐색)를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 노드를 방문할 때 "현재 노드가 부모의 오른쪽 자식인지" 여부를 불리언 플래그로 함께 전달하는 것입니다.
알고리즘 단계
- 노드(node)와 불리언 값(add)을 매개변수로 받는 dfs() 함수를 정의합니다.
- node가 null이면 즉시 반환합니다.
- node의 왼쪽 자식과 오른쪽 자식이 모두 null이고 add가 true라면, 현재 노드는 오른쪽 잎이므로 ret에 노드의 값을 더합니다.
- 왼쪽 자식에 대해서는 dfs(left, false)로 재귀 호출합니다.
- 오른쪽 자식에 대해서는 dfs(right, true)로 재귀 호출합니다.
메인 함수에서의 처리
- 결과 변수 ret을 0으로 초기화합니다.
- dfs(root, true)를 호출합니다. 루트는 원래 누군가의 오른쪽 자식이 아니지만, 트리가 루트 하나뿐인 특수한 경우도 처리하기 위한 설계 선택입니다.
- ret을 반환합니다.
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 ret = 0;
void dfs(TreeNode* node, bool add){
if(!node)
return;
if(!node->left && !node->right && add){
ret += node->val;
}
dfs(node->left, false);
dfs(node->right, true);
}
int solve(TreeNode* root) {
ret = 0;
dfs(root, true);
return ret;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(10);
root->left->left = new TreeNode(15);
root->left->right = new TreeNode(7);
cout << ob.solve(root);
}
입력
TreeNode *root = new TreeNode(3); root->left = new TreeNode(9); root->right = new TreeNode(10); root->left->left = new TreeNode(15); root->left->right = new TreeNode(7);
출력
17
동작 과정 살펴보기
위 예제 트리에서 DFS가 진행되는 순서를 추적해 보면 다음과 같습니다.
- 루트 3에서 시작하여 왼쪽 자식 9는 add=false로, 오른쪽 자식 10은 add=true로 탐색합니다.
- 노드 9의 왼쪽 자식 15는 add=false로 방문되므로, 잎 노드임에도 불구하고 합산되지 않습니다.
- 노드 9의 오른쪽 자식 7은 add=true이고 자식이 없으므로 ret에 더해집니다. (ret = 7)
- 노드 10 역시 add=true이고 자식이 없으므로 ret에 더해집니다. (ret = 17)
- 최종적으로 17이 반환됩니다.
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이 h에 비례합니다. 균형 잡힌 트리에서는 O(log n)이며, 한쪽으로 치우친 편향 트리의 최악의 경우 O(n)까지 증가할 수 있습니다.