All problems

Same Tree

Easy · tree dfs

You are given the roots of two binary trees, p and q. Return True if the two trees are identical, and False otherwise.

Two trees are identical when they have the same shape and every pair of matching nodes holds the same value. Matching means the same position: the left child of one tree is compared with the left child of the other, and the right with the right. Two empty trees are identical, and an empty tree is never identical to a tree with at least one node.

Examples

Example 1

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

Output: True

Both trees have the same shape and every matching node has the same value.

Example 2

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

Output: False

Both trees hold the values 1 and 2, but in p the 2 is a left child and in q it is a right child, so the shapes differ.

Example 3

Input: p = [1, 2, 1], q = [1, 1, 2]

Output: False

The shapes match, but the left children are 2 and 1, so the values differ.

Constraints