이 문제에서는 하나의 이진 트리가 주어지며, 우리의 과제는 주어진 이진 트리에서 모든 오른쪽 리프(right leaf) 노드의 합을 구하는 것입니다. 여기서 오른쪽 리프 노드란 부모 노드의 오른쪽 자식이면서 동시에 자식이 없는 노드를 의미합니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력 :
출력 : 8
설명 −
트리의 오른쪽 리프 노드 : 1, 7 합 = 1 + 7 = 8
위 트리에서 노드 1은 노드 4의 오른쪽 자식이자 리프 노드이고, 노드 7은 노드 6의 오른쪽 자식이자 리프 노드입니다. 따라서 두 값의 합인 8이 최종 결과가 됩니다.
접근 방법 1: 재귀(Recursion)
가장 간단한 해결 방법은 루트부터 리프까지 트리를 순회하는 것입니다. 순회 중 어떤 노드가 오른쪽 리프 노드라면 그 값을 합계에 더하고, 전체 트리의 순회가 끝나면 합계를 출력합니다.
알고리즘의 동작 과정은 다음과 같습니다.
- 현재 노드의 오른쪽 자식이 리프 노드인지 확인합니다.
- 리프 노드라면 해당 노드의 값을 합계에 더하고, 아니라면 오른쪽 서브트리에 대해 재귀 호출을 계속 진행합니다.
- 왼쪽 서브트리에 대해서도 재귀 호출을 수행합니다.
구현 예제
#include <iostream>
using namespace std;
struct Node {
int key;
struct Node* left, *right;
};
Node *newNode(int k) {
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
bool isLeafNode(Node *node) {
if (node == NULL)
return false;
if (node->left == NULL && node->right == NULL)
return true;
return false;
}
int findRightLeavesSum(Node *root) {
int sum = 0;
if (root != NULL) {
if (isLeafNode(root->right))
sum += root->right->key;
else
sum += findRightLeavesSum(root->right);
sum += findRightLeavesSum(root->left);
}
return sum;
}
int main() {
struct Node *root = newNode(5);
root->left = newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right = newNode(7);
cout<<"The sum of right leaves of the tree is "<<findRightLeavesSum(root);
return 0;
}
출력
The sum of right leaves of the tree is 8
접근 방법 2: 반복문과 스택(DFS)
재귀 대신 명시적인 스택을 사용하여 깊이 우선 탐색(DFS)을 수행할 수도 있습니다. 스택에서 노드를 꺼낼 때마다 그 노드의 오른쪽 자식이 리프 노드인지 확인하고, 리프 노드라면 값을 합계에 더합니다. 모든 노드를 처리한 후 최종 합계를 출력합니다.
구현 예제
#include<bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* left, *right;
};
Node *newNode(int k) {
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
int findRightLeavesSum(Node* root) {
if(root == NULL) return 0;
stack<Node*> treeNodes;
treeNodes.push(root);
int sum = 0;
while(treeNodes.size() > 0){
Node* currentNode = treeNodes.top();
treeNodes.pop();
if (currentNode->right != NULL){
treeNodes.push(currentNode->right);
if(currentNode->right->right == NULL &&
currentNode->right->left == NULL){
sum += currentNode->right->key;
}
}
if (currentNode->left != NULL)
treeNodes.push(currentNode->left);
}
return sum;
}
int main(){
Node *root = newNode(5);
root->left= newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right= newNode(7);
cout<<"The sum of right leaves of the tree is "<<findRightLeavesSum(root);
return 0;
}
출력
The sum of right leaves of the tree is 8
접근 방법 3: 큐(BFS)
세 번째 방법은 너비 우선 탐색(BFS)을 활용하는 것입니다. 큐에는 노드와 함께 해당 노드가 오른쪽 자식인지 여부를 나타내는 불리언 값을 함께 저장합니다. 큐에서 꺼낸 노드가 리프 노드이면서 오른쪽 자식이라면 그 값을 합계에 더하고, 탐색이 끝나면 합계를 출력합니다.
구현 예제
#include<bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* left, *right;
};
Node *newNode(int k) {
Node *node = new Node;
node->key = k;
node->right = node->left = NULL;
return node;
}
int findRightLeavesSum(Node* root) {
if (root == NULL)
return 0;
queue<pair<Node*, bool> > treeNodes;
treeNodes.push({ root, false });
int sum = 0;
while (!treeNodes.empty()) {
Node* temp = treeNodes.front().first;
bool isRightChild = treeNodes.front().second;
treeNodes.pop();
if (!temp->left && !temp->right && isRightChild)
sum = sum + temp->key;
if (temp->left) {
treeNodes.push({ temp->left, false });
}
if (temp->right) {
treeNodes.push({ temp->right, true });
}
}
return sum;
}
int main(){
Node *root = newNode(5);
root->left= newNode(4);
root->right = newNode(6);
root->left->left = newNode(2);
root->left->right = newNode(1);
root->right->left = newNode(9);
root->right->right= newNode(7);
cout<<"The sum of right leaves of the tree is "<<findRightLeavesSum(root);
return 0;
}
출력
The sum of right leaves of the tree is 8
복잡도 분석
세 가지 방법 모두 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)(n은 노드의 개수)입니다. 공간 복잡도는 재귀 방식의 경우 호출 스택으로 인해 O(h)(h는 트리의 높이)이며, 스택이나 큐를 사용하는 반복 방식은 최악의 경우 O(n)입니다.