LeetCode 100. Same Tree

Post by ailswan Sep.10, 2023

100. Same Tree

Tree, DFS, BFS, Binary Tree  · 

Problem Statement

link: https://leetcode.com/problems/same-tree/ https://leetcode.cn/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:

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

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

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

Solution Approach

The approach is to use a depth-first search (DFS) to traverse both trees simultaneously and compare the values and structure at each step.

Algorithm

  1. If both trees are empty, return True.
  2. If one of the trees is empty, return False.
  3. Compare the values of the current nodes of both trees.
  4. Recursively compare the left subtrees and the right subtrees.

Implement

    class Solution:
      if not p and not q:
                return True
            if not p or not q:
                return False
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)