C++로 이진 트리에서 리프 노드 간 최장 경로 출력하기

이번 튜토리얼에서는 주어진 이진 트리(Binary Tree)에서 한 리프 노드에서 다른 리프 노드까지 이어지는 가장 긴 경로를 출력하는 프로그램을 다루겠습니다.

다시 말해, 이진 트리의 지름(diameter)에 포함된 모든 노드를 출력해야 합니다. 여기서 지름(또는 너비)이란 한 끝 노드에서 다른 끝 노드까지 이르는 가장 긴 경로에 존재하는 노드의 개수를 의미합니다.

이 문제를 해결하려면 먼저 높이(height) 함수를 활용해 이진 트리의 지름을 계산합니다. 그다음 왼쪽 서브트리와 오른쪽 서브트리에서 각각 가장 긴 경로를 찾아낸 뒤, 마지막으로 왼쪽 부분의 노드들 → 루트 노드 → 오른쪽 부분의 노드들 순서로 출력하면 지름에 해당하는 전체 경로를 얻을 수 있습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left, *right;
};
struct Node* create_node(int data){
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f){
    if (root == NULL)
        return 0;
    int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
    int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
    if (ans < 1 + left_tree_height + right_tree_height){
        ans = 1 + left_tree_height + right_tree_height;
        k = root;
        lh = left_tree_height;
        rh = right_tree_height;
    }
    return 1 + max(left_tree_height, right_tree_height);
}
void print_roottonode(int ints[], int len, int f){
    int i;
    if (f == 0){
        for (i = len - 1; i >= 0; i--) {
            printf("%d ", ints[i]);
        }
    }
    else if (f == 1) {
        for (i = 0; i < len; i++) {
            printf("%d ", ints[i]);
        }
    }
}
void print_pathr(Node* node, int path[], int pathLen, int max, int& f){
    if (node == NULL)
    return;
    path[pathLen] = node->data;
    pathLen++;
    if (node->left == NULL && node->right == NULL) {
        if (pathLen == max && (f == 0 || f == 1)) {
            print_roottonode(path, pathLen, f);
            f = 2;
        }
    }
    else {
        print_pathr(node->left, path, pathLen, max, f);
        print_pathr(node->right, path, pathLen, max, f);
    }
}
void calc_diameter(Node* root){
    if (root == NULL)
        return;
    int ans = INT_MIN, lh = 0, rh = 0;
    int f = 0;
    Node* k;
    int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
    int lPath[100], pathlen = 0;
    print_pathr(k->left, lPath, pathlen, lh, f);
    printf("%d ", k->data);
    int rPath[100];
    f = 1;
    print_pathr(k->right, rPath, pathlen, rh, f);
}
int main(){
    struct Node* root = create_node(12);
    root->left = create_node(22);
    root->right = create_node(33);
    root->left->left = create_node(45);
    root->left->right = create_node(57);
    root->left->right->left = create_node(26);
    root->left->right->right = create_node(76);
    root->left->left->right = create_node(84);
    root->left->left->right->left = create_node(97);
    calc_diameter(root);
    return 0;
}

실행 결과

97 84 45 22 57 26

코드 동작 원리

tree_height 함수는 재귀적으로 각 노드의 왼쪽·오른쪽 서브트리 높이를 구한 뒤, 두 높이의 합에 1을 더한 값이 현재까지의 최댓값보다 크면 해당 노드를 지름의 중심 노드 후보로 저장합니다. 이 과정에서 왼쪽 경로의 길이(lh)와 오른쪽 경로의 길이(rh)도 함께 기록됩니다.

이후 print_pathr 함수가 중심 노드의 왼쪽 서브트리와 오른쪽 서브트리를 순회하며, 길이가 기록된 값과 일치하는 리프 노드까지의 경로를 찾아냅니다. 왼쪽 경로는 역순으로, 오른쪽 경로는 정방향으로 출력되므로 최종적으로 리프 → 루트 → 리프로 이어지는 가장 긴 경로가 화면에 표시됩니다.

위 예제 트리에서는 노드 97에서 출발하여 84, 45, 22, 57, 26을 거치는 경로가 지름에 해당하며, 실행 결과에서 이를 확인할 수 있습니다.