🔗 🟡 1367. Linked List in Binary Tree 1650

tags: `Weekly Contest 178` `樹(Tree)` `DFS` `BFS` `鏈結串列(Linked List)` `二元樹(Binary Tree)`

題意

給定一個二元樹的根節點 $root$ 和一個鏈結串列的第一個節點 $head$ 。

如果在二元樹中，存在一條一直向下的路徑，且每個點的數值恰好一一對應以 $head$ 為首的鏈結串列中每個節點的值，那麼請你返回 True，否則返回 False。

一直向下的路徑的意思是：從樹中某個節點開始，一直連續向下的路徑。

思路：枚舉(Enumeration)

首先簡化問題。如果固定根結點 $root$ ，那麼我們只需要檢查是否存在一條從根節點一直向下的路徑，其數值一一對應鏈結串列中每個節點的值即可。為此我們可以定義一個遞迴函數 dfs(head, root)，用於檢查從根節點 $root$ 開始是否能匹配鏈結串列 $head$ 。

如果鏈結串列已經匹配完(head == nullptr)，返回 True
如果樹已經走完但鏈結串列還沒匹配完(root == nullptr)，返回 False
如果當前根節點不匹配(head.val != root.val)，返回 False
否則，繼續檢查鏈結串列的下一個節點是否能匹配樹的左子節點或右子節點 (dfs(head.next, root.left) or dfs(head.next, root.right))

由於樹上的任何一個節點都可以作為根節點，因此我們可以枚舉樹上的每一個節點，並調用 dfs 函數。只要有一條路徑匹配即可。故也能將 isSubPath 視為一個遞迴函數：

若從當前位置開始，則直接調用 dfs(head, root)
若從左右子樹開始，則遞迴調用 isSubPath(head, root.left) 和 isSubPath(head, root.right)

需要注意，若 root 為空，則直接返回 False，否則會造成遞迴無法結束。

複雜度分析

時間複雜度： $\mathcal{O}(n \times \min(2^{m+1}, n))$ $O (n \times min (2^{m + 1}, n))$ ，其中 $n$ $n$ 是樹的節點數， $m$ $m$ 是鏈結串列的節點數。
- 在最壞情況下，我們需要遍歷二元樹的每一個節點，需要 $O(n)$ 的時間。
- 每次調用 dfs 函數最多需要檢查一棵高度為 $m$ 的子樹，其最多有 $2^{m+1}$ 個節點，但由於整棵樹的節點樹為 $n$ ，所以實際上我們需要檢查的節點數為兩者中的最小值。
空間複雜度： $O(h)$ $O (h)$ ，其中 $h$ $h$ 是樹的高度。
- 在調用 isSubPath 時，會遞歸調用 dfs 函數，但在最壞情況下，遞迴深度還是不會超過樹的高度。

class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        if not root:
            return False
        # 從當前位置開始，或從左右子樹開始
        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
    
    def dfs(self, head, root):
        if not head: # LinkedList 中所有值皆能在 Tree 中找到
            return True
        if not root: # 還沒走完 LinkedList 但 Tree 已經走完
            return False
        if head.val != root.val: # 該位置無法對應
            return False
        # 繼續往下一個位置尋找(左或右)
        return self.dfs(head.next, root.left) or self.dfs(head.next, root.right)

class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (root == nullptr) return false;
        return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
    }

    bool dfs(ListNode* head, TreeNode* root) {
        if (head == nullptr) return true;
        if (root == nullptr) return false;
        if (head->val != root->val) return false;
        return dfs(head->next, root->left) || dfs(head->next, root->right);
    }
};