###### tags: `leetcode`
# leecode 1367
題目:https://leetcode.com/problems/linked-list-in-binary-tree/

# 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(h,r):
            if h==None:
                return True
            elif r==None:
                return False
            else:
                return (h.val==r.val)*(dfs(h.next,r.left)+dfs(h.next,r.right))
        if head==None:
            return True
        elif root==None:
            return False
        else:
            return dfs(head,root)+self.isSubPath(head,root.left)+self.isSubPath(head,root.right)

解題邏輯:當head的頭對到root的頭就繼續對下去，否則返回原點(對頭的地方)並對左右子樹做main
當head的頭對到root的頭就繼續對下去，這是DFS
做DFS否則返回原點(對頭的地方)並對左右子樹做main，這邊要做recursive main

O(N * min(L,H))
N = tree size, H = tree height, L = list length