aboutsummaryrefslogtreecommitdiff
path: root/linked_list_binary_tree.py
diff options
context:
space:
mode:
Diffstat (limited to 'linked_list_binary_tree.py')
-rw-r--r--linked_list_binary_tree.py104
1 files changed, 104 insertions, 0 deletions
diff --git a/linked_list_binary_tree.py b/linked_list_binary_tree.py
new file mode 100644
index 0000000..b9e8bd0
--- /dev/null
+++ b/linked_list_binary_tree.py
@@ -0,0 +1,104 @@
+# 1367. Linked List in Binary Tree
+
+"""
+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.
+"""
+
+
+# Definition for singly-linked list.
+class ListNode(object):
+ def __init__(self, val=0, next=None):
+ self.val = val
+ self.next = next
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def isSubPath(self, head, root):
+ """
+ :type head: ListNode
+ :type root: TreeNode
+ :rtype: bool
+ """
+
+ def dfs(head, root):
+ if not head:
+ return True
+ if not root:
+ return False
+ return root.val == head.val and (
+ dfs(head.next, root.left) or dfs(head.next, root.right)
+ )
+
+ if not head:
+ return True
+ if not root:
+ return False
+ return (
+ dfs(head, root)
+ or self.isSubPath(head, root.left)
+ or self.isSubPath(head, root.right)
+ )
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.isSubPath(
+ head=[4, 2, 8],
+ root=[
+ 1,
+ 4,
+ 4,
+ None,
+ 2,
+ 2,
+ None,
+ 1,
+ None,
+ 6,
+ 8,
+ None,
+ None,
+ None,
+ None,
+ 1,
+ 3,
+ ],
+ )
+ )
+ print(
+ obj.isSubPath(
+ head=[1, 4, 2, 6],
+ root=[
+ 1,
+ 4,
+ 4,
+ None,
+ 2,
+ 2,
+ None,
+ 1,
+ None,
+ 6,
+ 8,
+ None,
+ None,
+ None,
+ None,
+ 1,
+ 3,
+ ],
+ )
+ )