【Description】
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

 3
/ \

4 5
/
1 2
Given tree t:
4
/
1 2
Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

 3
/ \

4 5
/
1 2
/
0
Given tree t:
4
/
1 2
Return false.

【Idea】
判斷兩樹是否相同 + 二叉樹遍歷dfs。
（這才不是個(gè)easy吧...

【Solution】

# 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 isSubtree(self, s: TreeNode, t: TreeNode) -> bool:

        def isSame(root1, root2):
            if not root1 and not root2:
                return True 
            elif not root1 or not root2:
                return False
            elif root1.val != root2.val:
                return False
            return isSame(root1.left, root2.left) and isSame(root1.right, root2.right)
        
        stack = [s]
        while s or stack:
            while s:
                stack.append(s)
                if isSame(s, t):
                    return True 
                s = s.left
            s = stack.pop()
            s = s.right 
        return False