Problem
Given a binary tree rootand 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.
Solution
Starting from a node of the binary tree, we search left and right child and try to match the numbers in the linked list. If either left or right path matches, we could return true, otherwise false.
Therefore, to solve this question, we could simply do a search mentioned above starting from every node in the binary tree.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool runner(ListNode* head, TreeNode* root) {
if (!head) return true;
if (!root) return false;
bool left = false, right = false;
if (head->val == root->val) {
left = runner(head->next, root->left);
right = runner(head->next, root->right);
}
else return false;
return left || right;
}
bool isSubPath(ListNode* head, TreeNode* root) {
if (!head) return true;
if (!root) return false;
return runner(head, root) || isSubPath(head, root->left) ||
isSubPath(head, root->right);
}
};