이진 트리가 하나 주어졌을 때, 이 트리에서 가장 긴 연속 경로(Longest Consecutive Path)의 길이를 찾아야 합니다. 여기서 말하는 경로는 값이 증가하는 방향이거나 감소하는 방향일 수 있습니다. 예를 들어 [1,2,3,4]와 [4,3,2,1]은 모두 유효한 경로로 간주되지만, [1,2,4,3]처럼 증감이 섞인 경로는 유효하지 않습니다.
흥미로운 조건은, 경로가 자식 → 부모 → 자식(child-parent-child) 형태를 가질 수도 있다는 점입니다. 즉, 반드시 부모에서 자식으로 내려가는 순서일 필요는 없습니다.
예를 들어 입력이 다음과 같다면,
출력은 3이 됩니다. 가장 긴 연속 경로가 [1, 2, 3] 또는 [3, 2, 1]이기 때문입니다.
알고리즘 접근 방식
이 문제는 각 노드를 기준으로 증가 경로의 최대 길이와 감소 경로의 최대 길이를 동시에 추적하는 재귀적 후위 순회(post-order traversal)로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- solveUtil() 함수를 정의합니다. 이 함수는 노드를 인자로 받습니다.
- 노드가 null이면 {0, 0} 쌍(pair)을 반환합니다. (first: 증가 경로 길이, second: 감소 경로 길이)
- left = solveUtil(노드의 왼쪽 자식)을 호출합니다.
- right = solveUtil(노드의 오른쪽 자식)을 호출합니다.
- {1, 1}로 초기화된 temp 쌍을 선언합니다.
- 왼쪽 자식이 존재하고 그 값이 node.val + 1과 같다면:
temp.first = max(temp.first, 1 + left.first)
ans = max(ans, temp.first) - 오른쪽 자식이 존재하고 그 값이 node.val + 1과 같다면:
temp.first = max(temp.first, 1 + right.first)
ans = max(ans, temp.first) - 왼쪽 자식이 존재하고 그 값이 node.val - 1과 같다면:
temp.second = max(temp.second, 1 + left.second)
ans = max(ans, temp.second) - 오른쪽 자식이 존재하고 그 값이 node.val - 1과 같다면:
temp.second = max(temp.second, 1 + right.second)
ans = max(ans, temp.second) - ans = max(ans, temp.first + temp.second - 1)로 갱신합니다. 이 단계가 바로 한 노드를 꼭짓점으로 하는 '자식 → 부모 → 자식' 경로를 처리하는 핵심 부분입니다.
- temp를 반환합니다.
메인 함수에서는 ans를 0으로 초기화한 뒤 solveUtil(root)를 호출하고, 마지막에 ans를 반환하면 됩니다.
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;
}
};
class Solution {
public:
int ans = 0;
pair<int, int> solveUtil(TreeNode* node){
if (!node) {
return { 0, 0 };
}
pair<int, int> left = solveUtil(node->left);
pair<int, int> right = solveUtil(node->right);
pair<int, int> temp = { 1, 1 };
if (node->left && node->left->val == node->val + 1) {
temp.first = max(temp.first, 1 + left.first);
ans = max(ans, temp.first);
}
if (node->right && node->right->val == node->val + 1) {
temp.first = max(temp.first, 1 + right.first);
ans = max(ans, temp.first);
}
if (node->left && node->left->val == node->val - 1) {
temp.second = max(temp.second, 1 + left.second);
ans = max(ans, temp.second);
}
if (node->right && node->right->val == node->val - 1) {
temp.second = max(temp.second, 1 + right.second);
ans = max(ans, temp.second);
}
ans = max({ ans, temp.first + temp.second - 1 });
return temp;
}
int longestConsecutive(TreeNode* root){
ans = 0;
solveUtil(root);
return ans;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
cout << (ob.longestConsecutive(root));
}
입력
TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3);
출력
3
복잡도 분석
시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이가 트리의 높이(h)에 비례합니다.