C++로 이진 트리에서 만들 수 있는 최대 길이 사이클 구하기

이진 트리가 하나 주어졌을 때, 해당 트리에서 형성할 수 있는 최대 길이의 사이클(cycle)을 찾는 것이 이 글의 목표입니다. 핵심 아이디어는 간단합니다. 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 최대 높이를 각각 구한 뒤, 이 두 경로를 루트를 통해 연결하면 가장 긴 사이클을 얻을 수 있습니다.

예를 들어 위 트리에서 최대 길이 사이클은 1-2-3-4-7-6 또는 1-6-7-4-3-2-1이며, 그 길이는 6입니다.

입력 및 출력 예시

예시 1

입력 − 트리

출력 − 최대 사이클 길이: 5

설명 − 왼쪽 서브트리의 최대 높이는 3, 오른쪽 서브트리의 최대 높이는 1입니다. 따라서 사이클 길이는 3+1+1=5가 됩니다. 사이클은 1-2-3-4-6 또는 1-6-4-3-2 입니다.

예시 2

입력 − 트리

출력 − 최대 사이클 길이: 7

설명 − 왼쪽 서브트리의 최대 높이는 3, 오른쪽 서브트리의 최대 높이 역시 3입니다. 사이클 길이는 3+3+1=7이 되며, 사이클은 5-4-2-1-8-7-6 또는 5-6-7-8-1-2-4-5 입니다.

알고리즘 접근 방식

• 노드의 값을 저장하는 int형 data 멤버와 다른 노드를 가리키는 left, right 포인터를 public 멤버로 갖는 treenode 클래스를 정의합니다.
• newNode(int data) 함수는 전달받은 값으로 새 노드를 생성하고, 좌우 포인터를 NULL로 초기화합니다.
• newNode() 함수를 반복적으로 호출하여 트리를 구성합니다.
• maxheight(treenode* root) 함수는 매개변수로 받은 노드를 루트로 하는 서브트리의 최대 높이를 재귀적으로 계산해 반환합니다.
• 루트가 NULL이면 높이는 0이므로 즉시 0을 반환합니다.
• lheight와 rheight는 각각 maxheight(root->left)와 maxheight(root->right)의 재귀 호출을 통해 왼쪽·오른쪽 서브트리의 높이를 구합니다.
• 두 값 중 더 큰 값에 1을 더해(현재 노드 포함) 반환합니다.
• main 함수에서는 루트의 왼쪽 서브트리 최대 높이(maxlheight)와 오른쪽 서브트리 최대 높이(maxrheight)를 저장합니다.
• 루트 자신을 포함해야 하므로 최종 사이클 길이는 maxlheight + maxrheight + 1이 됩니다.
• 계산된 사이클 길이를 화면에 출력합니다.

이 방식은 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 재귀 호출 스택 깊이만큼의 메모리를 추가로 사용합니다.

C++ 예제 코드

#include <bits/stdc++.h>
using namespace std;

// 트리 노드 클래스
class treenode {
public:
    int data;
    treenode* left;
    treenode* right;
};

// 현재 루트의 왼쪽·오른쪽 서브트리 중 최대 높이를 구하는 함수
int maxheight(treenode* root) {
    if (root == NULL)
        return 0;
    else {
        int lheight = maxheight(root->left);
        int rheight = maxheight(root->right);
        // 최대 높이 계산
        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}

// 트리 노드 생성 함수
treenode* newNode(int data) {
    treenode* Node = new treenode();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return (Node);
}

int main() {
    treenode *root = newNode(6);
    root->left = newNode(8);
    root->right = newNode(9);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->right = newNode(7);
    root->left->right->right->left = newNode(2);

    int maxlheight = maxheight(root->left);
    int maxrheight = maxheight(root->right);

    cout << "Maximum length cycle: " << maxlheight + maxrheight + 1;
    return 0;
}

실행 결과

Maximum length cycle: 6