문제 개요
루트(root)에서 임의의 리프(leaf) 노드까지 이어지는 모든 경로가 하나의 유효한 시퀀스를 형성하는 이진 트리가 있습니다. 이때 정수 배열 arr의 값을 순서대로 이어 붙여 만든 수열이 이 트리에 실제로 존재하는 루트-리프 경로와 정확히 일치하는지 확인해야 합니다.
유효한 시퀀스의 조건을 정리하면 다음과 같습니다.
- 배열의 첫 번째 값은 루트 노드의 값과 일치해야 합니다.
- 배열의 각 값은 경로상의 노드 값과 순서대로 일치해야 합니다.
- 배열의 마지막 값은 반드시 리프 노드(자식이 없는 노드)의 값과 일치해야 하며, 리프에 도달하는 시점에 배열도 정확히 끝나야 합니다.
예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.
arr = [0, 1, 0, 1]이라면 출력은 True입니다. 경로 0 → 1 → 0 → 1이 실제로 존재하기 때문입니다(그림에서 초록색 경로). 참고로 이 트리에서 만들 수 있는 다른 유효한 시퀀스로는 0 → 1 → 1 → 0과 0 → 0 → 0이 있습니다.
접근 방법: DFS 재귀 탐색
이 문제는 깊이 우선 탐색(DFS)을 활용한 재귀 함수로 자연스럽게 해결할 수 있습니다. 핵심 아이디어는 루트에서 출발해 배열의 값을 한 칸씩 진행하며 노드 값과 비교하고, 리프 노드에 도달하는 순간 배열의 끝에도 정확히 도달했는지 확인하는 것입니다.
알고리즘 단계
- solve(node, v, idx) 함수를 정의합니다. idx는 0으로 초기화합니다.
- node가 NULL이면 false를 반환합니다.
- idx가 배열 v의 크기보다 크거나 같으면 false를 반환합니다.
- 현재 노드의 값이 v[idx]와 다르면 false를 반환합니다.
- 현재 노드가 자식이 없는 리프 노드라면, idx가 배열의 마지막 인덱스(v.size() - 1)와 같을 때만 true를 반환합니다.
- 리프가 아니라면 왼쪽 자식과 오른쪽 자식에 대해 각각 solve(node->left, v, idx + 1)과 solve(node->right, v, idx + 1)를 재귀 호출하고, 둘 중 하나라도 true이면 true를 반환합니다.
- 메인 함수에서는 solve(root, arr)를 호출하여 최종 결과를 얻습니다.
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:
bool solve(TreeNode* node, vector <int>& v, int idx = 0){
if(!node) return false;
if(idx >= v.size()) return false;
if(node->val != v[idx]) return false;
if(!node->left && !node->right){
return idx == v.size() - 1;
}
return solve(node->left, v, idx + 1) || solve(node->right, v, idx + 1);
}
bool isValidSequence(TreeNode* root, vector<int>& arr) {
return solve(root, arr);
}
};
main(){
TreeNode *root = new TreeNode(0);
root->left = new TreeNode(1); root->right = new TreeNode(0);
root->left->left = new TreeNode(0); root->left->right = new
TreeNode(1);
root->right->left = new TreeNode(0);
root->left->left->right = new TreeNode(1);
root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);
Solution ob;
vector<int> v = {0,1,0,1};
cout << (ob.isValidSequence(root, v));
}
입력
TreeNode *root = new TreeNode(0); root->left = new TreeNode(1); root->right = new TreeNode(0); root->left->left = new TreeNode(0); root->left->right = new TreeNode(1); root->right->left = new TreeNode(0); root->left->left->right = new TreeNode(1); root->left->right->left = new TreeNode(0); root->left->right->right = new TreeNode(0);
출력
1
출력값 1(true)은 배열 [0, 1, 0, 1]이 트리 안에서 실제로 존재하는 유효한 루트-리프 경로임을 의미합니다.
복잡도 분석
- 시간 복잡도: O(N) — 최악의 경우 트리의 모든 노드를 한 번씩 방문하게 됩니다(N은 노드의 총 개수).
- 공간 복잡도: O(H) — 재귀 호출 스택의 깊이는 트리의 높이 H에 비례합니다.