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:
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:
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:
- The number of nodes in the tree will be in the range
[1, 2500]
. - The number of nodes in the list will be in the range
[1, 100]
. 1 <= Node.val <= 100
for each node in the linked list and binary tree.
Approach 01:
-
C++
-
Python
class Solution { public: bool isSubPath(ListNode* linkedListHead, TreeNode* treeRoot) { if (treeRoot == nullptr) return false; return hasPathStartingFromNode(linkedListHead, treeRoot) || isSubPath(linkedListHead, treeRoot->left) || isSubPath(linkedListHead, treeRoot->right); } private: bool hasPathStartingFromNode(ListNode* currentListNode, TreeNode* currentTreeNode) { if (currentListNode == nullptr) return true; if (currentTreeNode == nullptr) return false; return currentListNode->val == currentTreeNode->val && (hasPathStartingFromNode(currentListNode->next, currentTreeNode->left) || hasPathStartingFromNode(currentListNode->next, currentTreeNode->right)); } };
class Solution: def isSubPath(self, linkedListHead: Optional[ListNode], treeRoot: Optional[TreeNode]) -> bool: if treeRoot is None: return False return self.hasPathStartingFromNode(linkedListHead, treeRoot) or self.isSubPath(linkedListHead, treeRoot.left) or self.isSubPath(linkedListHead, treeRoot.right) def hasPathStartingFromNode(self, currentListNode: Optional[ListNode], currentTreeNode: Optional[TreeNode]) -> bool: if currentListNode is None: return True if currentTreeNode is None: return False return currentListNode.val == currentTreeNode.val and (self.hasPathStartingFromNode(currentListNode.next, currentTreeNode.left) or self.hasPathStartingFromNode(currentListNode.next, currentTreeNode.right))
Time Complexity
- Main Function
isSubPath
:The function
isSubPath
recursively traverses the entire binary tree to check if any path starting from any node matches the linked list. In the worst case, it will check every node in the tree, leading to a time complexity of \( O(n) \), wheren
is the total number of nodes in the binary tree. - Helper Function
hasPathStartingFromNode
:For each node of the tree, the helper function
hasPathStartingFromNode
checks for the presence of the linked list path starting from that node. In the worst case, this function can go through all nodes of the linked list for each tree node, leading to a time complexity of \( O(m) \), wherem
is the length of the linked list. - Overall Time Complexity:
Combining both parts, the overall time complexity is \( O(n \cdot m) \), where
n
is the number of nodes in the binary tree andm
is the length of the linked list.
Space Complexity
- Auxiliary Space (Recursion):
The space complexity is determined by the recursion stack. The depth of the recursion stack can go up to the height of the binary tree in the worst case, which is \( O(h) \), where
h
is the height of the binary tree.Additionally, for each call to
hasPathStartingFromNode
, there can be a recursion depth up to the length of the linked listm
. Thus, the auxiliary space complexity could be \( O(h + m) \). - Overall Space Complexity:
The overall space complexity is \( O(h + m) \), where
h
is the height of the binary tree andm
is the length of the linked list.