100. Same Tree

# 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:
        """ tc O(N) sc O(N)
        """
        if not p and not q: 
            return True 
        if (p and not q) or (q and not p): 
            return False 
        if q.val != p.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """ tc O(N) sc O(N)
        """
        st = [(p,q)]
        while st:
            p,q = st.pop()
            # if not p and not q: continue can be ignore
            if p and q  and p.val == q.val:
                st.append((p.left,q.left))
                st.append((p.right, q.right))
            elif p or q:
                return False
        return True