이진 트리가 하나 주어졌을 때, 노드 값이 연속적으로 1씩 증가하는 순서로 이루어진 가장 긴 경로의 길이를 계산해야 합니다. 모든 노드는 기본적으로 길이 1짜리 경로로 간주합니다.
예를 들어 아래와 같은 이진 트리가 입력으로 주어진다고 가정해 보겠습니다.
이 경우 (11 → 12 → 13)이 가장 긴 연속 증가 경로이므로 출력 결과는 3이 됩니다.
해결 접근 방법
이 문제는 재귀(DFS) 방식으로 해결할 수 있습니다. 핵심 아이디어는 각 노드를 방문하면서 이전 노드 값과 비교하여 연속성을 확인하고, 연속되지 않는 지점에서는 새로운 경로를 시작하는 것입니다.
구체적인 단계는 다음과 같습니다.
- solve() 함수를 정의합니다. 이 함수는 세 개의 매개변수(root, prev_data, prev_length)를 받습니다.
- root가 NULL이면 지금까지 누적된 prev_length를 반환합니다.
- cur_data에 현재 노드의 값을 저장합니다.
- cur_data가 prev_data + 1과 같다면(값이 연속적으로 증가하는 경우), 왼쪽 자식과 오른쪽 자식을 탐색한 결과 중 최댓값을 반환합니다. 이때 경로 길이는 prev_length + 1로 늘립니다.
- 값이 연속되지 않는다면 현재 노드에서 새로운 경로를 시작합니다. newPathLen은 solve(왼쪽 자식, cur_data, 1)와 solve(오른쪽 자식, cur_data, 1) 중 최댓값입니다.
- 마지막으로 prev_length와 newPathLen 중 더 큰 값을 반환합니다.
메인 함수에서는 다음과 같이 처리합니다.
- root가 NULL이면 0을 반환합니다.
- 그렇지 않으면 solve(root, root->val - 1, 0)을 호출합니다. 첫 번째 노드도 길이 1의 경로로 포함되도록 prev_data를 루트 값보다 1 작게 설정하는 것이 핵심입니다.
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;
}
};
int solve(TreeNode *root, int prev_data, int prev_length){
if (!root)
return prev_length;
int cur_data = root->val;
if (cur_data == prev_data+1){
return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
}
int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
return max(prev_length, newPathLen);
}
int maxLen(TreeNode *root){
if (root == NULL)
return 0;
return solve(root, root->val-1, 0);
}
int main(){
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(11);
root->right = new TreeNode(9);
root->left->left = new TreeNode(13);
root->left->right = new TreeNode(12);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(8);
cout << maxLen(root);
return 0;
}입력
TreeNode *root = new TreeNode(10); root->left = new TreeNode(11); root->right = new TreeNode(9); root->left->left = new TreeNode(13); root->left->right = new TreeNode(12); root->right->left = new TreeNode(13); root->right->right = new TreeNode(8);
출력
3
복잡도 분석
이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 노드의 개수입니다. 공간 복잡도는 재귀 호출 스택 깊이에 의해 결정되며, 최악의 경우(편향된 트리) O(n), 균형 잡힌 트리의 경우 O(log n)입니다.