Linked List in Binary Tree — LeetCode 1367 Python Solution
MediumTreeDepth-First SearchLinked ListBinary Tree
- Problem
- #1367
- Pattern
- Linked List
- Reading time
- 5 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
def dfs(head, root):
if head is None:
return True
if root is None or root.val != head.val:
return False
return dfs(head.next, root.left) or dfs(head.next, root.right)
if root is None:
return False
return (
dfs(head, root)
or self.isSubPath(head, root.left)
or self.isSubPath(head, root.right)
)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n^2) |
| Space | O(n) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1367. Linked List in Binary Tree is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1367. Linked List in Binary Tree?
- LeetCode 1367. Linked List in Binary Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1367. Linked List in Binary Tree?
- The Python solution on this page runs in O(n^2).
- What is the space complexity of LeetCode 1367. Linked List in Binary Tree?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1367. Linked List in Binary Tree cover?
- LeetCode 1367. Linked List in Binary Tree is tagged Tree, Depth-First Search, Linked List and Binary Tree on LeetCode.