noodleProblems/
Same Tree
#105

Same Tree

AlgorithmeasyTreeDepth First SearchBreadth First SearchBinary Tree

Given the roots of two binary trees p and q, return true if they are **structurally identical** and every corresponding pair of nodes holds the same value.

Two empty trees are the same. Two trees differ if either their shape differs (a node present in one and absent in the other) or any matched pair of nodes disagrees in value.

Each tree is given as a level-order array where null marks a missing child: [1, 2, 3] is root 1 with children 2 and 3.

Example cases

  • identical
    in p = [1,2,3]213q = [1,2,3]213
    out true
  • shape differs
    in p = [1,2]21q = [1,null,2]12
    out false
    Same values but 2 is a left child in one and a right child in the other.
  • value differs
    in p = [1,2,1]211q = [1,1,2]112
    out false

Constraints

  • The number of nodes in each tree is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4
Saved
p =
[1,2,3]
q =
[1,2,3]