对称二叉树

🟢 Easy · 🏷️ 树、递归、DFS · LeetCode#101

📖 题目

判断一棵二叉树是否轴对称。

    1           对称 ✓
   / \
  2   2
 / \ / \
3  4 4  3

💡 思路

前面几道树题的递归函数都只接收一个节点，这题不一样——判断对称要同时看两个节点是不是互为镜像，所以需要一个接收两个参数的辅助函数。

镜像的条件：

• 两个都是空节点 → 对称
• 只有一个是空 → 不对称
• 两个都在，但值不相等 → 不对称
• 值相等，则递归检查 left.left 跟 right.right、left.right 跟 right.left——位置是交叉对调的，这跟判断两棵树是否相同（对应位置直接比）不一样，是"对称"这个词在递归条件里的体现

💻 代码

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isMirror(root.left, root.right) if root else True

    def isMirror(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
        if left is None and right is None:
            return True
        if left is None or right is None:
            return False
        if left.val != right.val:
            return False
        return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

时间复杂度 O(n)，空间复杂度 O(h)，h 是树高。