Same Tree
01 · Problem
Given the roots of two binary trees, root1 and root2, decide whether they are identical. Two trees count as identical only when they have exactly the same shape and every pair of nodes in matching positions holds the same value.
Return true if they are identical and false otherwise. The tree is given in level-order, with null marking a missing child. Two empty trees are identical.
02 · Examples
root1 = [1,2,3], root2 = [1,2,3]
true
Both trees have root 1 with left child 2 and right child 3.
root1 = [1,2], root2 = [1,null,2]
false
In the first tree 2 is a left child; in the second it is a right child, so the shapes differ.
root1 = [1,2,1], root2 = [1,1,2]
false
The shapes match, but the left children hold 2 and 1 respectively.
03 · Constraints
- 01The number of nodes in each tree is in the range [0, 100].
- 02-104 <= Node.val <= 104
- 03Either tree (or both) may be empty, and the two trees may have different numbers of nodes.
- 04The tree height is at most 100, and the tree may be fully skewed.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.