[LeetCode] 1367. Linked List in Binary Tree 二叉樹中的鏈表

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.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

The number of nodes in the tree will be in the range [1, 2500].
The number of nodes in the list will be in the range [1, 100].
1 <= Node.val <= 100 for each node in the linked list and binary tree.

這道題說是給了一棵二叉樹，還給了一個鏈表，問能不能在二叉樹中找到一條路徑 path，使得其正好是給定的結點鏈表，題目中例子中的圖很好的解釋了題意。這里的二叉樹的路徑并沒有限制要從根節點開始，結束位置也不一定要是葉結點，那么理論上不同路徑的數量就太多了。如果是想先求出二叉樹的所有路徑后，再來跟結點鏈表比較的話，一是太麻煩了，二是效率也不高。最好的辦法還是在遍歷的過程中就直接開始比較了，比較的方法就是當遇到和此時鏈表頭結點相同的結點時，開始進行下一個結點的比較，由于路徑可以去左子結點或者右子結點，所以左右子結點都要去嘗試，這里用遞歸就非常合適了，只要左右子結點任意一個返回 true 了，那么就說明成功匹配了。如果當前的結點和鏈表頭結點的值不相同的話，則分別再去左右子結點進行嘗試，此時左右子結點還是跟原來的鏈表首結點去比較，因為之前沒有匹配上，同樣，只要左右子結點的遞歸任意一個返回 true 了，就說明成功匹配上了。根據這種思路寫出的代碼如下（注意這種下面這種解法是錯誤的，之后會分析）：

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

上面的解法雖然簡潔，但實際上是錯誤的解法，這里可以舉一個反例：head = [4,2,2], root = [4,2,null,4,null,2]，二叉樹的結構如下所示：

上面解法錯誤的原因是當 head 匹配完4和2之后，下一個2匹配不上了，因為二叉樹中是4，但此時卻沒有從開頭的4重新匹配，而是繼續匹配鏈表中剩下的那個2，這樣在跳過二叉樹中的第二個4之后，最后一個2就匹配上了，整個就返回了 true。但實際上是錯誤的，給定的二叉樹中并沒有一個連續的 4->2->2 路徑，相當于找到了類似于字符串中的子序列，而要求的卻是子串。正確的做法實際上是對每個結點都當做起始點來匹配一下，這里用一個子函數 dfs 來匹配，匹配的方法就是看鏈表和二叉樹的當前結點值是否相等，是的話再對左右子結點調用遞歸，只要任意一個返回 true 就行了。在主函數中，調用完 dfs 后，還要分別對左右子結點調用主函數的遞歸，這樣才能保證把每個結點都當起始點來匹配，才能避免上面那個反例的情況，參見代碼如下：

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1367

參考資料：

https://leetcode.com/problems/linked-list-in-binary-tree

https://leetcode.com/problems/linked-list-in-binary-tree/solutions/524881/python-recursive-solution-o-n-l-time/

https://leetcode.com/problems/linked-list-in-binary-tree/solutions/524821/c-simple-recursion/

LeetCode All in One 題目講解匯總(持續更新中...)