457. Identical Trees
Two archivists each keep a record of a family lineage as a binary tree, stored in a and b. Before merging their archives they must decide whether the two records are exactly the same.
Return true if the trees have the same shape and every pair of corresponding nodes holds the same value; return false otherwise. Two empty trees are identical, while an empty tree and a non-empty tree are not. A node having only a left child differs from a node having only a right child.
Example 1
- Input:
- a = [4,2,6,null,3], b = [4,2,6,null,3]
- Output:
- true
- Explanation:
Both trees have the same shape and the same values at every position.
Example 2
- Input:
- a = [4,2], b = [4,null,2]
- Output:
- false
- Explanation:
The value 2 is a left child in the first tree but a right child in the second, so the shapes differ.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)