forked from luliyucoordinate/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1367.cpp
34 lines (29 loc) · 773 Bytes
/
1367.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution
{
public:
bool isSubPath(ListNode* head, TreeNode* root)
{
f.emplace_back(-1);
int i = -1;
ListNode* node = head;
while (node != nullptr)
{
while (i != -1 && node != nullptr && node->val != arr[i]) i = f[i];
i++;
f.emplace_back(i);
arr.emplace_back(node->val);
node = node->next;
}
return dfs(root, 0);
}
private:
vector<int> arr, f;
bool dfs(TreeNode* node, int u)
{
if (node == nullptr) return false;
while (u != -1 && node->val != arr[u]) u = f[u];
u++;
if (u == arr.size()) return true;
return dfs(node->left, u) || dfs(node->right, u);
}
};