Same Tree

You get two binary trees, p and q. Return true if they are identical, and false if not.

Identical trees have the same shape. Nodes in the same spot also hold the same value. Two empty trees count as identical.

In the examples, each tree is written row by row from the top. Each row goes left to right. NULL marks a missing child.

Example 1:

     p             q
     5             5
    / \           / \
   8   2         8   2
    \             \
     4             4

Input: p = [5,8,2,NULL,4], q = [5,8,2,NULL,4]
Output: true
Explanation: Both trees have the same shape.
Each spot holds the same value in both trees.

Example 2:

     p             q
     4             4
    /             / \
   7             7   1
  /
 1

Input: p = [4,7,NULL,1], q = [4,7,1]
Output: false
Explanation: Both trees hold 4, 7 and 1.
In p, the 1 is the left child of 7.
In q, the 1 is the right child of 4.

Example 3:

     p             q
     6             6
    / \           / \
   4   9         9   4

Input: p = [6,4,9], q = [6,9,4]
Output: false
Explanation: The shapes match.
But the left child of 6 is 4 in p and 9 in q.

Constraints:

• Each tree has 0 to 10,000 nodes.
• Each value is a whole number from -10,000 to 10,000.
• A value can repeat.
• Each tree is at most 400 levels deep.