노드들로 구성된 이진 트리가 주어졌을 때, 이 트리에 포함된 모든 잎 노드(리프 노드) 값의 곱을 구하는 것이 목표입니다.
잎 노드란 자식 노드를 하나도 가지고 있지 않은 말단 노드를 의미합니다. 트리에서 루트 노드는 항상 부모 노드 역할만 수행하며, 그 외의 노드들은 부모 노드이거나 자식 노드가 될 수 있습니다. 따라서 왼쪽 포인터와 오른쪽 포인터가 모두 NULL인 노드가 바로 잎 노드입니다.
문제 예시
입력:
잎 노드: 23, 34, 25
곱: 23 × 34 × 25 = 19550
트리를 순회하여 자식이 없는 노드인 23, 34, 25를 찾아내고, 세 값을 모두 곱하면 19550이 됩니다.
접근 방법
- 노드 데이터를 입력받습니다.
- 루트 노드에서 시작하여 왼쪽 하위 트리 또는 오른쪽 하위 트리로 이동하면서 모든 노드를 순회(traversal)합니다.
- 왼쪽 포인터와 오른쪽 포인터가 모두 NULL인 노드를 발견하면, 해당 값을 곱셈 변수에 누적합니다.
- 순회가 끝나면 곱이 저장된 변수의 값을 출력합니다.
알고리즘
시작
1단계 → 노드 구조체를 생성하고 temp, next, head를 구조체 노드 포인터로 선언
struct node
int data
node *left, *right 생성
끝
2단계 → 트리에 새 노드를 삽입하는 함수 선언
node* new_node(int data)
node* temp = new node() 설정
temp→data = data 설정
temp→left = temp→right = NULL 설정
return temp
끝
3단계 → 모든 잎 노드의 곱을 구하는 함수 선언
void leaf(node* root, int &product)
IF (!root)
Return
끝
IF (!root→left && !root→right)
product *= root→data
끝
leaf(root→left, product) 호출
leaf(root→right, product) 호출
4단계 → main() 함수에서
node* root = new_node(10) 생성
root→left = new_node(20) 설정
root→left→left = new_node(30) 설정
int product = 1 설정
leaf(root, product) 호출
product 출력
종료
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 노드 구조체 정의
struct node {
int data;
node *left, *right;
};
// 트리의 새 노드를 생성하는 함수
node* new_node(int data) {
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// 트리의 모든 잎 노드의 곱을 구하는 함수
void leaf(node* root, int &product) {
if (!root)
return;
if (!root->left && !root->right)
product *= root->data;
leaf(root->left, product);
leaf(root->right, product);
}
int main() {
node* root = new_node(10);
root->left = new_node(20);
root->left->left = new_node(30);
root->left->right = new_node(40);
root->right = new_node(50);
root->right->right = new_node(60);
root->right->left = new_node(70);
int product = 1;
leaf(root, product);
cout << "product of a leaf nodes are :" << product;
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
product of a leaf nodes are :5040000
이 예제 트리에서 잎 노드는 30, 40, 60, 70이며, 이 네 값을 곱하면 30 × 40 × 60 × 70 = 5040000이 됩니다.
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택이 사용되므로 트리의 높이(h)에 비례하는 메모리가 필요합니다. 균형 잡힌 트리라면 O(log n), 편향된 트리라면 최악의 경우 O(n)이 됩니다.