SameTree

Problem

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

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

Constraints:

• The number of nodes in both trees is in the range [0, 100].

• -10:sup:`4`<= Node.val <= 10:sup:`4`

Solution

Two tree are equal if and only if their roots are equal and their left and right subtrees are equal. To check if the left and right subtrees are equal, we can use recursion. If both roots are None, then they are equal. If one is None and the other is not, then they are not equal.

Pattern

Tree, Depth-First Search, Breadth-First Search, Binary Tree

Code

class TreeNode:
    """Node in a binary tree.
    """

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def isSameTree(p: TreeNode | None, q: TreeNode | None) -> bool:
    """Checks if two binary trees with roots ``p`` and ``q`` are equal.
    """
    if p is None and q is None:
        return True
    elif p is None or q is None:
        return False
    else:
        return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Test

>>> from SameTree import TreeNode, isSameTree
>>> root1 = TreeNode(1, TreeNode(2), TreeNode(3))
>>> root2 = TreeNode(1, TreeNode(2), TreeNode(3))
>>> isSameTree(root1, root2)
True
>>> root1 = TreeNode(1, None, TreeNode(2))
>>> root2 = TreeNode(1, TreeNode(2), None)
>>> isSameTree(root1, root2)
False
>>> root1 = TreeNode(1, TreeNode(2), TreeNode(1))
>>> root2 = TreeNode(1, TreeNode(1), TreeNode(2))
>>> isSameTree(root1, root2)
False

class SameTree.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

SameTree.isSameTree(p: TreeNode | None, q: TreeNode | None) → bool

Checks if two binary trees with roots p and q are equal.