100.Same_Tree_(Easy).md

100. Same Tree (Easy)

Date and Time: May 28, 2024 (EST)
Update: Jul 15, 2024, 22:57 (EST)

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

Question:

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1, 2, 3], q = [1, 2, 3]

Output: true

Example 2:

Input: p = [1, 2], q = [1, null, 2]

Output: false

Example 3:

Input: p = [1, 2, 1], q = [1, 1, 2]

Output: false

KeyPoints:

For recursion version, we just want to compare if two trees' left/right subtrees are different, which are the same three conditions we check: 1. if p, q are None. 2. if p or q is None (when one node exists, but another tree's node doesn't exist). 3. if p.val != q.val.

For BFS version, we use two queues queueP, queueQ to store root's left/right nodes. If both queues are not empty, we check the same above three conditions, and add the root's left/right nodes into each queue. Finally, make sure both queues are empty so they are the same.

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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # BFS, Queue FIFO
        queue_p = [p]
        queue_q = [q]
        while queue_p and queue_q:
            p, q = queue_p.pop(), queue_q.pop()
            # When both nodes are none or null, they are the same
            if not p and not q:
                continue
            # When one of the node is None (Example 2)
            if not p or not q:
                return False
            # When values are not the same
            if p.val != q.val:
                return False
            # Update queues
            queue_p.append(p.left)
            queue_p.append(p.right)
            queue_q.append(q.left)
            queue_q.append(q.right)
        # Both queues should be empty in the end
        return not queue_p and not queue_q    # Same as return len(queueP) == 0 and len(queueQ) == 0

Recursion Solution:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # When both p, q are none, they are the same
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)