Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 이진 트리의 가장 긴 연속 수열 경로 찾기

문제 개요

하나의 이진 트리가 주어졌을 때, 이 트리에서 가장 긴 연속 수열 경로(longest consecutive sequence path)의 길이를 찾아야 합니다. 여기서 '경로'란 어떤 시작 노드에서 출발하여 부모-자식 연결 관계를 따라 트리 내의 임의의 노드까지 이어지는 노드들의 나열을 의미합니다.

중요한 조건은, 연속 경로가 반드시 부모 노드에서 자식 노드 방향으로만 진행되어야 하며, 자식에서 부모로 거슬러 올라가는 역방향 이동은 허용되지 않는다는 점입니다.

예제로 이해하기

예를 들어 다음과 같은 이진 트리가 입력으로 주어졌다고 가정해 봅시다.

C++로 구현하는 이진 트리의 가장 긴 연속 수열 경로 찾기

이 경우 출력 결과는 3입니다. 가장 긴 연속 수열 경로가 3 → 4 → 5이며, 이 경로의 길이가 3이기 때문입니다.

알고리즘 접근 방법

이 문제는 DFS(깊이 우선 탐색) 기반의 재귀 함수로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 노드를 방문할 때마다 '현재까지 이어진 연속 경로의 길이'를 함께 전달하는 것입니다. 구체적인 단계는 다음과 같습니다.

  1. solveUtil(node, prev, len = 1) 함수를 정의합니다. len은 기본값 1로 초기화됩니다.
  2. node가 NULL이라면 함수를 그대로 종료합니다.
  3. prev + 1이 현재 노드의 값과 같은 경우(연속성이 유지되는 경우):
    • len을 1 증가시킵니다.
    • ans를 ans와 len 중 더 큰 값으로 갱신합니다.
    • 왼쪽 자식과 오른쪽 자식에 대해 solveUtil(자식, 현재 노드의 값, len)을 재귀 호출합니다.
  4. 그렇지 않은 경우(연속성이 끊긴 경우):
    • 왼쪽 자식과 오른쪽 자식에 대해 solveUtil(자식, 현재 노드의 값, 1)을 호출하여 새로운 경로를 시작합니다.
  5. solve(A) 함수를 정의합니다.
    • ans := 1로 초기화합니다.
    • solveUtil(A, -∞)를 호출합니다.
    • ans를 반환합니다.
  6. 메인 로직에서는:
    • root가 NULL이면 0을 반환합니다.
    • 그 외에는 solve(root)의 결과를 반환합니다.

C++ 구현 예제

아래의 전체 구현 코드를 통해 동작 과정을 더 명확히 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
public:
    int ans;
    void solveUtil(TreeNode* node, int prev, int len = 1){
        if (!node)
            return;
        if (prev + 1 == node->val) {
            len++;
            ans = max(ans, len);
            solveUtil(node->left, node->val, len);
            solveUtil(node->right, node->val, len);
        }
        else {
            solveUtil(node->left, node->val, 1);
            solveUtil(node->right, node->val, 1);
        }
    }
    int solve(TreeNode* A){
        ans = 1;
        solveUtil(A, INT_MIN);
        return ans;
    }
    int longestConsecutive(TreeNode* root){
        if (!root)
            return 0;
        return solve(root);
    }
};
int main(){
    Solution ob;
    TreeNode *root = new TreeNode(1);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(2);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(5);
    cout << (ob.longestConsecutive(root));
}

입력

TreeNode *root = new TreeNode(1);
root->right = new TreeNode(3);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(4);
root->right->right->right = new TreeNode(5);

출력

3

복잡도 분석

시간 복잡도: O(n). 모든 노드를 정확히 한 번씩 방문하므로 노드의 개수 n에 비례합니다.

공간 복잡도: O(h). 재귀 호출 스택의 깊이가 트리의 높이 h에 비례하며, 균형 잡힌 트리라면 O(log n), 최악의 경우(편향 트리) O(n)이 됩니다.