You are given p and q, the roots of two binary trees (either may be empty).
Return true if the trees are identical, with the same shape and equal values in matching
places, and false otherwise.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the right child of 2.
Example 1
- Input
- p = [4, 2, 6, 1, 3], q = [4, 2, 6, 1, 3]
- Output
- true
Example 2
- Input
- p = [7, 5], q = [7, null, 5]
- Output
- false
Constraints
- Each tree holds 0 to 500 nodes.
- Every value is between −10⁴ and 10⁴.
Show the pattern
Trees
Two trees are the same when their roots match and their left subtrees and right subtrees are each the same. The answer for a pair of nodes comes from the answers for their children: recursion.
See trees in a visualiserShow the approach
Recurse on pairs of nodes, one from each tree. Two empty trees match. If only one is empty, or the two values differ, they don't. Otherwise the trees are identical exactly when the left subtrees are identical and the right subtrees are identical. The recursion stops at the first difference.
Time: O(n), n the smaller tree's size · Space: O(h) for the recursion, h the height