Problem
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.
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);
}
};