Binary Trees Depth first: return a value up
346. Same Tree
You are given p and q, the root nodes of two binary trees. Return true if the two trees are the same,
and false otherwise.
Two trees are the same when they have the same shape, and each node holds the same value as the node in the same place in the other tree. Two empty trees are the same.
The examples write a tree level by level, from left to right, with null where a child is missing. So
p = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: p = [6, 2, 9, null, 4], q = [6, 2, 9, 4]
falseExplanation: Both trees hold 6, 2, 9 and 4, and only 4 sits in a different place. In p it is the right child of 2,
and in q it is the left child of 2.
Example 2
Input: p = [3, -1, 8, null, null, 5]
q = [3, -1, 8, null, null, 5]
trueExplanation: In both trees, 3 has the children −1 and 8, and 8 has the left child 5.
Example 3
Input: p = [], q = [0]
falseExplanation: p is empty, and q has one node.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes in each tree ≤ 105-109 ≤ Node.val ≤ 109- Each tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.