Are Two Binary Trees the Same
You are given p and q, the roots of two binary trees.
Return true if the two trees are the same, and false otherwise. Two trees are the same when they have exactly the same shape, and every node in one tree has the same value as the node in the same place in the other tree.
Two empty trees are the same. An empty tree and a non-empty tree are not.
How the input is shown
A tree is shown as a list in level order: the root first, then each level from left to right. null marks a missing child, and missing children of a missing node are not listed. For example, [4, 2, 7, null, 3] is root 4 with left child 2 and right child 7, and 2 has only a right child, 3. An empty tree is [].
Note
- Having the same values is not enough. A child on the left is not the same as a child on the right.
- Hint: compare the two roots. If both are missing, they match. If only one is missing, or the values differ, they do not match. Otherwise the trees are the same exactly when the left subtrees are the same and the right subtrees are the same.
Examples
Example 1
- Input:
- [3,5,1], [3,5,1]
- Output:
- true
Both trees have root 3, left child 5 and right child 1.
Example 2
- Input:
- [3,5], [3,null,5]
- Output:
- false
In the first tree 5 is the left child of 3. In the second tree 5 is the right child. The values match, but the shapes do not.
Example 3
- Input:
- [2,4,6], [2,4,7]
- Output:
- false
The shapes match, but the right child is 6 in the first tree and 7 in the second.
Constraints
0 <=number of nodes in each tree<= 40-100 <= Node.val <= 100
Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.