Easy

Same Tree

018

Given two binary trees encoded as level-order arrays with -100000 as null, return true if they are structurally identical with equal values.

EXAMPLES

Example 1

Input
{
  "p": [
    1,
    2,
    3
  ],
  "q": [
    1,
    2,
    3
  ]
}

Output
true

FUNCTION SHAPE

p: intArrayq: intArray→bool

SOLUTION NOTE

This introduces comparing two trees simultaneously. Two empty trees are the same, but an empty and non-empty tree are different. This is postorder - we need results from subtrees first.

Reveal reference solution +

pythonREFERENCE

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    # Base cases: if either tree is empty
    if not p and not q:
        return True
    if not p or not q:
        return False

    # Check current nodes and recursively check subtrees
    return (p.val == q.val and
            self.isSameTree(p.left, q.left) and
            self.isSameTree(p.right, q.right))

TimeO(min(n1, n2))

SpaceO(min(h1, h2))

Open on LeetCode ↗