문제 개요
루트 노드와 왼쪽 자식, 오른쪽 자식을 가진 하나의 이진 트리(Binary Tree)가 있다고 가정해 보겠습니다. 이때 구해야 할 값은 부모 노드의 왼쪽 자식 위치에 있는 리프(잎) 노드들의 데이터 총합입니다.
예시
입력:
출력:
15
설명: 주어진 이진 트리에서 부모의 왼쪽에 위치한 리프 노드는 9, 4, 2이며, 이들의 합은 9 + 4 + 2 = 15입니다. 따라서 출력값은 15가 됩니다.
문제 해결 접근 방법
이 문제는 재귀(Recursion)를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 현재 노드의 왼쪽 자식이 존재하는지 먼저 확인하고, 그 왼쪽 자식이 더 이상 자식을 가지지 않는다면(즉, 리프 노드라면) 해당 노드의 값을 결과에 더하는 것입니다. 이후 오른쪽 서브트리에 대해서도 같은 과정을 재귀적으로 반복하면 전체 트리를 한 번의 순회로 처리할 수 있습니다.
알고리즘 단계
- 루트 노드와 왼쪽·오른쪽 자식을 가진 이진 트리를 입력으로 받습니다.
- 정수형 함수
leftLeafSum(treenode* root)는 루트 노드를 입력받아 부모의 왼쪽에 위치한 모든 리프 노드의 합을 반환합니다. - 루트 노드가 NULL이면 0을 반환합니다.
- 루트 노드의 왼쪽 자식이 존재하고 그 자식이 리프 노드라면, 해당 노드의 값을 더한 뒤 오른쪽 서브트리를 재귀적으로 탐색합니다.
- 그 외의 경우에는 왼쪽 자식과 오른쪽 자식 각각에 대해 재귀적으로 합을 구해 더한 값을 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode *left;
treenode *right;
};
struct treenode* createNode(int d) {
struct treenode* root = new treenode;
root->data = d;
root->left = NULL;
root->right = NULL;
return root;
}
int leftLeafSum(treenode* root) {
if (root == NULL)
return 0;
// 왼쪽 자식이 존재하고, 그 자식이 리프 노드인 경우
if (root->left && !root->left->left && !root->left->right)
return root->left->data + leftLeafSum(root->right);
return leftLeafSum(root->left) + leftLeafSum(root->right);
}
int main() {
struct treenode* root = NULL;
root = createNode(4);
root->left = createNode(2);
root->right = createNode(2);
root->left->right = createNode(7);
root->left->left = createNode(5);
root->right->left = createNode(5);
root->right->right = createNode(7);
int sum = leftLeafSum(root);
cout << sum << endl;
return 0;
}
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력
10
설명: 이 예제에서 부모의 왼쪽 자식 위치에 있으면서 자식을 가지지 않는 노드는 값이 5인 두 노드뿐입니다. 따라서 왼쪽 리프 노드의 합은 5 + 5 = 10이 됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다. (n은 전체 노드 수)
- 공간 복잡도: O(h) — 재귀 호출 스택이 트리의 높이(h)만큼 사용됩니다. 트리가 한쪽으로 치우친 편향 트리일 경우 O(n)까지 증가할 수 있습니다.