Same Tree
Easy · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the roots p and q of two binary trees, return True if the trees are the same, and False otherwise.
Two trees are the same when they have exactly the same shape and every pair of nodes in matching positions holds the same value. A child on the left is not the same as a child on the right, even with the same value.
The node type and two helpers are provided:
Examples
Input: p = [1,2,3], q = [1,2,3] Output: True
Same shape and the same value everywhere.
Input: p = [1,2], q = [1,None,2] Output: False
In p the 2 is a left child; in q it is a right child, so the shapes differ.
Input: p = [1,2,1], q = [1,1,2] Output: False
The shapes match, but the children’s values are swapped.
Constraints
- 0 <= number of nodes in each tree <= 100
- -10^4 <= Node.val <= 10^4
Approaches
- Serialize both trees and compare the strings — time O(n), space O(n)
Follow-up
Can you do it without recursion? And how would you test whether one tree appears as a subtree of another (LeetCode 572)?
Related problems
Start free on Cariara · Coding problems · System design studio
