aboutsummaryrefslogtreecommitdiff
path: root/linked_list_binary_tree.py
blob: b9e8bd0353f71d916ef4699b78f7caa5a3840509 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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,
            ],
        )
    )