# 1367-1

Mar 20th, 2021
82
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2.  * Definition for singly-linked list.
3.  * struct ListNode {
4.  *     int val;
5.  *     ListNode *next;
6.  *     ListNode() : val(0), next(nullptr) {}
7.  *     ListNode(int x) : val(x), next(nullptr) {}
8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9.  * };
10.  */
11. /**
12.  * Definition for a binary tree node.
13.  * struct TreeNode {
14.  *     int val;
15.  *     TreeNode *left;
16.  *     TreeNode *right;
17.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
18.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
19.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
20.  * };
21.  */
22. class Solution {
23. public:
24.
25.     int n;
26.     vector<int> list, lps;
27.
29.         n = 0;
32.             n++;
34.         }
35.         lps.resize(n+1);
36.         lps.assign(n+1, 0);
37.     }
38.
39.     void kmpPreprocess(){
40.         int i, j;
41.         i=0; j=-1;
42.         lps[0] = -1;
43.         while(i<n){
44.             while(j>=0 && list[i] != list[j]) j = lps[j];
45.             i++, j++;
46.             lps[i] = j;
47.         }
48.     }
49.
50.     bool kmpSearch(TreeNode* root, int i){
51.         if(i == n) return true;
52.         if(!root) return false;
53.
54.         while(i>0 && root->val != list[i]) i = lps[i];
55.
56.         if(root->val == list[i]) i++;
57.         return (kmpSearch(root->left, i) || kmpSearch(root->right, i));
58.     }
59.
60.     bool isSubPath(ListNode* head, TreeNode* root) {