[LeetCode] 100. Same Tree

Problem : https://leetcode.com/problems/same-tree/

Use DFS approach to recursively compare every node on the 2 trees.

Time Complexity = O ( Min( M, N ) ).  

M = total nodes of P tree. N = total nodes of Q tree.

Recursive 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def preorder(node):
            if not node:
                yield None
            else:
                yield node.val
                yield from preorder(node.left)
                yield from preorder(node.right)
        
        return all(a == b for a, b in zip(preorder(p), preorder(q)))

Iterative 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(p, q)]
        
        while stack:
            p, q = stack.pop()
            
            if not p and not q:
                continue
                
            if not q or not p or p.val != q.val:
                return False
            
            stack.append((p.right, q.right))
            stack.append((p.left, q.left))
        
        return True

BFS 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # bfs
        pq = deque([p])
        qq = deque([q])
        
        while pq and qq:
            ptmp = deque()
            qtmp = deque()
            
            while pq and qq:
                ph = pq.popleft()
                qh = qq.popleft()
                
                if not ph and qh:
                    return False
                
                if ph and not qh:
                    return False
                
                if not ph and not qh:
                    continue
                
                if ph.val != qh.val:
                    return False
                
                ptmp.append(ph.left)
                ptmp.append(ph.right)
                qtmp.append(qh.left)
                qtmp.append(qh.right)
            
            if len(pq) != len(qq):
                return False
            
            pq = ptmp
            qq = qtmp
        
        return len(pq) == len(qq)

Edited on 04/21/2021. Update the recursive solution by using 'yield' and 'yield from'

Edited on 04/21/2021. Update the iterative solution.

Edited on 06/26/2021. Update the recursive solution by using the 'any' function.