이진 트리의 루트(root)와 첫 번째 노드가 head인 연결 리스트가 주어졌을 때, 연결 리스트의 모든 요소가 이진 트리에서 루트부터 아래 방향으로 이어지는 어떤 경로와 일치하면 True를, 그렇지 않으면 False를 반환해야 합니다.
예를 들어 다음과 같은 이진 트리가 있다고 가정해 보겠습니다.
이때 연결 리스트가 [1, 4, 2, 6]이라면, 이 값들이 트리의 한 하향 경로에 순서대로 존재하므로 출력 결과는 true가 됩니다.
문제 해결 접근 방법
이 문제는 재귀 호출과 메모이제이션(memoization)을 활용하여 해결할 수 있습니다. 핵심 아이디어는 트리의 각 노드에서 연결 리스트의 시작점과 값을 비교하고, 일치하는 경우 두 가지 선택지를 모두 고려하는 것입니다. 즉, 현재 노드에서 경로를 계속 이어갈 수 있는지 확인하고, 동시에 자식 노드에서 새로운 매칭을 시도할 수 있는지도 검사합니다.
구체적인 단계는 다음과 같습니다.
- 메모이제이션을 위한 맵(map) dp를 정의합니다.
- head(연결 리스트 노드), root(트리 노드), flag 세 개의 매개변수를 받는 solve() 메서드를 정의합니다.
- head가 null이면 true를 반환하고, root가 null이면 false를 반환합니다.
- dp에 이미 (head, root, flag) 조합의 결과가 저장되어 있다면 해당 값을 그대로 반환하여 중복 계산을 피합니다.
- head의 값과 root의 값이 같다면:
- ret := solve(head의 next, root의 left, false) 또는 solve(head의 next, root의 right, false)를 계산합니다.
- ret이 참이면 dp[head][root][flag] = true를 저장하고 반환합니다.
- 그렇지 않으면 dp[head][root][flag] = solve(head, root의 left, flag) 또는 solve(head, root의 right, flag)를 저장하고 반환합니다.
- 값이 같지 않은 경우, flag가 설정되어 있지 않다면(이미 경로 매칭 중이라면) dp[head][root][flag] = false를 반환합니다.
- flag가 설정되어 있다면 dp[head][root][flag] = solve(head, root의 left, flag) 또는 solve(head, root의 right, flag)를 반환합니다.
- 메인 함수에서는 solve(head, root, true)를 호출하여 최종 결과를 얻습니다.
여기서 flag의 역할이 중요합니다. flag가 true라면 아직 연결 리스트의 시작 지점을 찾지 못한 상태이므로 트리의 어느 노드에서든 매칭을 시도할 수 있습니다. 반면 flag가 false라면 이미 경로 매칭이 진행 중인 상태이므로 반드시 현재 노드의 자식으로만 이동해야 합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = 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:
map < ListNode*, map<TreeNode*, map <bool, bool>> > dp;
bool solve(ListNode* head, TreeNode* root, bool flag = true){
if(head == NULL) return true;
if(!root) return false;
if(dp.count(head) && dp[head].count(root) && dp[head]
[root].count(flag)) return dp[head][root][flag];
if(head->val == root->val){
bool ret = solve(head->next, root->left, false) ||
solve(head->next, root->right, false);
if(ret) return dp[head][root][flag] = true;
return dp[head][root][flag] = solve(head, root->left,
flag) || solve(head, root->right, flag);
}else if(!flag) return dp[head][root][flag] = false;
else
return dp[head][root][flag]= solve(head, root->left,
flag) || solve(head, root->right, flag);
}
bool isSubPath(ListNode* head, TreeNode* root) {
return solve(head, root);
}
};
main(){
vector<int> v = {1,4,2,6};
vector<int> v1 = {1,4,4,NULL,2,2,NULL,1,NULL,6,8,NULL,NULL,NULL,NULL,1,3};
ListNode *head = make_list(v);
TreeNode *root = make_tree(v1);
Solution ob;
cout << (ob.isSubPath(head, root));
}입력
[1,4,2,6] [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
출력
1
복잡도 분석
이 알고리즘의 시간 복잡도는 메모이제이션 덕분에 O(N × M)으로 분석할 수 있습니다. 여기서 N은 트리의 노드 수, M은 연결 리스트의 길이입니다. 각 (연결 리스트 노드, 트리 노드, flag) 조합은 최대 한 번만 계산되며, 공간 복잡도 역시 메모이제이션 테이블과 재귀 호출 스택으로 인해 O(N × M)입니다.