C++ 반복적 접근 방식으로 이진 트리의 모든 리프 노드를 왼쪽에서 오른쪽으로 출력하기

문제 개요

이 문제에서는 하나의 이진 트리가 주어지며, 트리의 모든 리프 노드를 왼쪽에서 오른쪽 순서로 출력해야 합니다. 여기서 리프 노드란 왼쪽이나 오른쪽에 자식 노드를 가지지 않는 노드를 의미합니다.

예시

예시를 통해 문제를 이해해 보겠습니다.

입력 −

출력 − 1 4 7

접근 방법

이 문제는 깊이 우선 탐색(Depth-First Search, DFS)을 활용하여 해결할 수 있습니다. 루트 노드부터 탐색을 시작하며, 방문한 노드가 리프 노드인지 검사합니다. 해당 노드가 리프 노드라면 그 값을 출력하고, 그렇지 않다면 왼쪽과 오른쪽 자식 서브트리를 차례로 탐색하여 모든 리프 노드를 찾아냅니다.

특히 왼쪽 서브트리를 먼저 탐색하기 때문에, 리프 노드들은 별도의 정렬 과정 없이도 자연스럽게 왼쪽에서 오른쪽 순서로 출력됩니다.

구현 예제

아래 코드는 위에서 설명한 해결 방법을 C++로 구현한 것입니다.

#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 printLTRLeafNodes(Node *root){
    if (!root)
        return;
    if (!root->left && !root->right) {
        cout<<root->data<<"\t";
        return;
    }
    if (root->left)
        printLTRLeafNodes(root->left);
    if (root->right)
        printLTRLeafNodes(root->right);
}
int main(){
    Node *root = insertNode(21);
    root->left = insertNode(5);
    root->right = insertNode(36);
    root->left->left = insertNode(2);
    root->right->left = insertNode(13);
    root->right->right = insertNode(4);
    root->right->left->left = insertNode(76);
    root->right->left->right = insertNode(9);
    root->right->right->left = insertNode(17);
    root->right->right->right = insertNode(2);
    cout<<"Leaf Nodes of the tree from left to rigth are :\n";
    printLTRLeafNodes(root);
    return 0;
}

출력 결과

Leaf Nodes of the tree from left to right are −
2 76 9 17 2

실행 결과를 보면, 예제 트리의 리프 노드인 2, 76, 9, 17, 2가 왼쪽에서 오른쪽 순서대로 정확하게 출력된 것을 확인할 수 있습니다. 이처럼 DFS 기반 탐색을 활용하면 이진 트리의 리프 노드를 손쉽게 순서대로 찾아낼 수 있습니다.