> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/depth-first-search/1367.-linked-list-in-binary-tree.md).

# 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:**

![](https://assets.leetcode.com/uploads/2020/02/12/sample_1_1720.png)

```
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:**

![](https://assets.leetcode.com/uploads/2020/02/12/sample_2_1720.png)

```
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:**

* `1 <= node.val <= 100` for each node in the linked list and binary tree.
* The given linked list will contain between `1` and `100` nodes.
* The given binary tree will contain between `1` and `2500` nodes.

给定linked list和二叉树，问二叉树中是否存在向下的path和list的值相等。类似字符串匹配的问题，可以主函数做分治并用另一个dfs函数对当前子树做list匹配，时间复杂度O(N \* M)。注意另一个用于匹配的dfs不能少，写成以下是错的：

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

问题在与当head->val != root->val时匹配没有及时返回，如l = \[1,2,6] t = \[1,4,2,6]时当4和2不等时依然会继续往下分治，而后面是能匹配上的因此整体会错误的返回true。

做串匹配还可以KMP，KMP本质可看作是dp，dp\[i]存以pattern字符串A中以i为底可匹配的最长前后缀长度。ptr初始为dp\[i -1]，当A\[i]和dp\[ptr]不等时，ptr = dp\[ptr]，直到相等或ptr == 0。比如aacaad的dp = \[0,1,0,1,2,0]，匹配d时先检查d和c是否相等，对应aac和aad；不等时往前跳到下一个与A\[i-1]匹配的位置，匹配a和d，对应aa和ad。过程如下，方块为未知i，△为prefix中下一个和A\[i]匹配的字符：![](https://pic2.zhimg.com/80/v2-a0c36e74615de266b219ae6fb12f5c4d_1440w.jpg)

生成dp数组后遍历树并做匹配，当不满足后把当前已匹配的看作suffix，把待匹配往前移动到对应prefix位置。时间复杂度O(N)。

思路参考自[lee251](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/linked-list-in-binary-tree/discuss/524881/Python-Recursive-Solution-O%28N%29-Time)。

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubPath(ListNode *head, TreeNode *root) {
        vector<int> A = {head->val}, dp = {0};
        int ptr = 0;
        head = head->next;
        while (head) {
            while (head && ptr && head->val != A[ptr]) ptr = dp[ptr - 1];
            ptr += head->val == A[ptr];
            A.push_back(head->val);
            dp.push_back(ptr);
            head = head->next;
        }
        return dfs(root, 0, A, dp);
    }

    bool dfs(TreeNode* root, int i, vector<int> &A, vector<int> &dp) {
        if (!root) return false;
        while (i && root->val != A[i]) i = dp[i - 1];
        i += root->val == A[i];
        return i == dp.size() || dfs(root->left, i, A, dp) || dfs(root->right, i, A, dp);
    }
};
```