Easy

Symmetric Tree

016

Given a binary tree encoded as level-order with -100000 as null, return true if it is symmetric.

EXAMPLES

Example 1

Input
{
  "root": [
    1,
    2,
    2,
    3,
    4,
    4,
    3
  ]
}

Output
true

FUNCTION SHAPE

root: intArray→bool

SOLUTION NOTE

Instead of comparing a node with itself, we compare corresponding nodes from left and right subtrees. The left subtree of tree1 must mirror the right subtree of tree2.

Reveal reference solution +

pythonREFERENCE

def isSymmetric(self, root: TreeNode) -> bool:
    def mirror(left: TreeNode, right: TreeNode) -> bool:
        if not left and not right:
            return True
        if not left or not right:
            return False

        return (left.val == right.val and
                mirror(left.left, right.right) and
                mirror(left.right, right.left))

    return not root or mirror(root.left, root.right)

# Alternative: compare tree with itself
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    def dfs(root1, root2):
        if not root1 or not root2:
            return not root1 and not root2
        return (root1.val == root2.val and
                dfs(root1.right, root2.left) and
                dfs(root1.left, root2.right))
    return dfs(root, root)

TimeO(n)

SpaceO(h)

Open on LeetCode ↗