# Leetcode 100. Same tree 相同的樹

## 題解思路
中序遍歷兩顆樹，只要兩個指針指向的節點不相同，或者是兩個指針指向的節點的值不同，就回傳False，如果遍歷到最後，就回傳True。

## DFS

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        
        stack = []
        cur_p, cur_q = p, q

        while cur_p or cur_q or stack:
            if (not cur_p and cur_q) or (cur_p and not cur_q):
                return False
            elif cur_p and cur_q:
                stack.append((cur_p,cur_q))
                cur_p = cur_p.left
                cur_q = cur_q.left
            elif not cur_p and not cur_q:
                node_p, node_q = stack.pop()
                if node_p.val != node_q.val:
                    return False
                cur_p = node_p.right
                cur_q = node_q.right
        return True

2023.07.12 AC (Recursion)

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def dfs(p: TreeNode, q: TreeNode):
            if not p and not q:
                return True
            if (not p and q) or (not q and p) or p.val != q.val:
                return False
            return dfs(p.left,q.left) and dfs(p.right,q.right)
        return dfs(p,q)