Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

LeetCode: Same Tree

Example:

Input: p = [1,2,3], q = [1,2,3]
Output: true

  1       1
 / \     / \
2   3   2   3

Input: p = [1,2], q = [1,null,2]
Output: false

  1       1
 /         \
2           2

Hints

Hint 1

Think about the base cases first: what if both trees are empty? What if only one is empty?

Hint 2

If both roots have the same value, the trees are the same if their left and right subtrees are also the same.

Hint 3

Use recursion to check both the left and right subtrees.