[LeetCode] 1367. Linked List in Binary Tree

https://leetcode.com/problems/linked-list-in-binary-tree/description/?envType=daily-question&envId=2024-09-07

leetcode - Linked List in Binary Tree

문제 유형 : 이진트리, 연결리스트

문제 난이도 : Medium

 

문제

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

 

이진트리의 root와 연결리스트의 head가 주어진다.

이진트리의 downward path중에서 연결리스트를 포함하고 있으면 true, 아니면 false를 반환하라.

 

풀이

은근히 트리키한 문제이다. 단순한 재귀로는 TLE에 걸린다.

중점은 어떻게 하면 재귀를 줄이냐인데, 꼭 필요한 재귀호출만 해주면 된다.

아니면, 브랜치의 순회를 빠르게 기각시키는것도 방법이다.

 

우선 트리의 현재 서브트리의 루트부터 연결리스트의 현재 위치와 대응시키는 순회를 하나 한다. 이 함수를 checkPath라 하자.

우선, 연결리스트 순회가 끝나면 true를 반환해야 한다.

그게 아닌데 서브트리 순회가 끝나면 false를 반환해야 한다.

지금 서브트리의 루트가 지금 연결리스트의 현재 위치와 대응하지 않는다면, false를 반환한다.

대응한다면, 다음 연결리스트 노드와 자식 서브트리들 중 한쪽이라도 대응된다면 true를 반환한다.

 

순회의 재귀적 구조를 만들기 위해서, 진입점인 isSubPath는

(현재 루트부터 checkPath) || (현재 루트의 왼쪽 자식부터 isSubPath호출) || (현재 루트의 오른쪽 자식부터 isSubPath호출)로 한다.

 

바로 길이 진행되는 경우만 끝까지 순회를 하고, 그게 아닐경우 빠른 탐색 포기를 한다.

이러면 모든 트리의 노드를 진입점으로 순회를 시작을 한 번씩 해본다.

게다가 or연산이기 때문에, 앞쪽 케이스에서 참이 확인되면, 뒤 케이스는 확인도 안하므로 효율적이다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();


class Solution {
public:
    bool checkPath(ListNode* head, TreeNode* root) {
        if (!head) return true;
        if (!root) return false;
        
        if (root->val == head->val) {
            return checkPath(head->next, root->left) || checkPath(head->next, root->right);
        }
        return false;
    }

    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!root) return false;
        
        return checkPath(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
    }
};