LeetCode 101: Symmetric Tree

Meta Data

#

Difficulty: easy First Attempt: 2022-08-02

• Submissions: Runtime Error ×2 → Accepted → Wrong Answer → Accepted ×4

Approach

#

Symmetric means the left subtree mirrors the right. Write a function checking whether two trees mirror each other (Tree Template 1): equal values, with a.left mirroring b.right (outer) and a.right mirroring b.left (inner).

My Attempts

#

The first two versions had syntax errors; a later one wrote left == right, comparing node objects instead of values, so two distinct nodes were never equal: [3, 3, 3] should be True but returned False.

Solution

#

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(a, b):
            if not a or not b:
                return a is b
            return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
        return mirror(root.left, root.right)

Complexity

#

Time O(n), space O(h).

Mistakes to Avoid

#

• Compare a.val == b.val; a == b checks whether they are the same object.

Interview Explanation

#

I write a mirror check: equal values, with outer pairs and inner pairs mirroring too, then apply it to the root’s two subtrees. Time O(n).