💬 Discord
Sign In
NeetCode #431LC-101EasyTrees
← Back to All Problems

#431 · #101 · Symmetric Tree(对称二叉树)

📌 Problem Statement & Constraints

Given the root of a binary tree, check whether it is mirror-symmetric around its centre. Constraints: the number of nodes is in [1, 1000], -100 <= Node.val <= 100.

💡 Core Algorithmic Approaches

  1. Two subtrees are mirrors when their roots have equal values and the left of one mirrors the right of the other.
  2. So recurse on the pair (a.left, b.right) and (a.right, b.left).
  3. The base cases are both None (symmetric) and exactly one None (not symmetric).
  4. Starting the comparison at (root.left, root.right) handles the whole tree.

💻 Benchmark Python3 Implementation

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

        return mirror(root.left, root.right) if root else True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each pair of mirrored nodes is compared once.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing (a.left, b.left): that tests equality, not symmetry; the pairing must be crossed.
  • Forgetting the exactly one None case: it would dereference None.
  • Serialising and comparing the string with its reverse: workable, but the null markers and delimiters must be right, and it uses O(n) space.
  • Handling the empty tree: it is trivially symmetric.