문제 개요
이 문제에서는 하나의 이진 트리(binary tree)가 주어지며, 트리에 포함된 모든 리프 노드(leaf node, 자식이 없는 노드)를 오른쪽에서 왼쪽 순서대로 출력해야 합니다.
예시를 통해 문제를 이해해 보겠습니다.
입력 −
출력 − 7 4 1
위 예시에서 트리의 리프 노드는 7, 4, 1이며, 오른쪽에서 왼쪽 순서로 출력됩니다.
이 문제를 해결하려면 이진 트리를 순회(traverse)해야 하며, 순회 방식은 크게 두 가지로 나눌 수 있습니다.
방법 1: 전위 순회(Preorder Traversal) – 재귀 사용
전위 순회는 재귀 호출을 기반으로 동작합니다. 일반적인 전위 순회는 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 탐색하지만, 이 문제에서는 출력 순서가 오른쪽에서 왼쪽이 되도록 루트 → 오른쪽 서브트리 → 왼쪽 서브트리 순서로 탐색합니다.
탐색 중 어떤 노드가 리프 노드(왼쪽 자식과 오른쪽 자식이 모두 없는 노드)라면 즉시 값을 출력하고, 그렇지 않다면 해당 노드의 자식들을 계속 탐색하여 리프 노드를 찾습니다.
구현 예제
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* insertNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findLeafNode(Node* root) {
if (!root)
return;
if (!root->left && !root->right) {
cout<<root->data<<"\t";
return;
}
if (root->right)
findLeafNode(root->right);
if (root->left)
findLeafNode(root->left);
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(8);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}실행 결과
Leaf nodes of the tree from right to left are − 18 2 98 8
방법 2: 후위 순회(Postorder Traversal) – 반복문과 스택 사용
두 번째 방법은 재귀 대신 반복(iteration)을 사용하는 후위 순회입니다. 스택(stack)을 활용해 노드 데이터를 저장하면서 트리를 후위 순회 방식(오른쪽 서브트리 → 왼쪽 서브트리 → 루트)으로 탐색하고, 그 과정에서 만나는 리프 노드를 출력합니다.
재귀 호출을 사용하지 않으므로 깊은 트리에서 재귀로 인한 스택 오버플로우를 피하고 싶을 때 유용한 접근 방식입니다.
구현 예제
#include<bits/stdc++.h>
using namespace std;
struct Node {
Node* left;
Node* right;
int data;
};
Node* insertNode(int key) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
void findLeafNode(Node* tree) {
stack<Node*> treeStack;
while (1) {
if (tree) {
treeStack.push(tree);
tree = tree->right;
} else {
if (treeStack.empty())
break;
else {
if (treeStack.top()->left == NULL) {
tree = treeStack.top();
treeStack.pop();
if (tree->right == NULL)
cout<<tree->data<<"\t";
}
while (tree == treeStack.top()->left) {
tree = treeStack.top();
treeStack.pop();
if (treeStack.empty())
break;
}
if (!treeStack.empty())
tree = treeStack.top()->left;
else
tree = NULL;
}
}
}
}
int main(){
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(18);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}실행 결과
Leaf nodes of the tree from right to left are − 18 2 98 8
정리
두 방법 모두 시간 복잡도는 O(n)으로 트리의 모든 노드를 한 번씩 방문합니다. 재귀 기반 전위 순회는 구현이 간결하고 직관적이며, 스택 기반 후위 순회는 명시적인 스택을 사용해 재귀 없이 동작한다는 장점이 있습니다. 상황에 맞는 방식을 선택하여 사용하면 됩니다.