对称二叉树

问题拆解

判断一棵树是否轴对称，容易卡在「对称」到底该怎么递归上。如果只盯着单个节点，会发现根本无从下手——对称描述的是根节点左右两半之间的关系，而不是某一个节点自己的属性。

所以要把问题改写成一个二元判断：左子树和右子树是否互为镜像。一旦这样定义，递归的结构就清楚了。

两棵树互为镜像的条件是：根值相等，且「甲的左」镜像「乙的右」、「甲的右」镜像「乙的左」。

递归比较镜像

def isSymmetric(root):
    def mirror(a, b):
        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)
                and mirror(a.right, b.left))

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

注意递归调用里的交叉方式：a.left 对 b.right、a.right 对 b.left。正是这个交叉，把「镜像」的语义落到了代码上。两个都为空说明对称到底了，只有一个为空则结构不对称。

迭代版思路

也可以用一个队列，每次成对取出两个应当镜像的节点做比较，再把它们的孩子按 (a.left, b.right) 和 (a.right, b.left) 成对入队。逻辑和递归完全一致，只是把调用栈换成了显式队列。

复杂度

指标	复杂度	原因
时间	O(n)	每个节点最多被比较一次
空间	O(h)	递归栈深度等于树高

可以迁移的模式

• 当「一棵树的性质」难以直接递归时，试着把它翻译成「两棵子树之间的关系」；
• 涉及镜像、对折、回文的问题，往往要让两个指针以相反方向同步推进；
• 二元递归的终止条件要覆盖「都空」和「只有一个空」两种情况。

把单参数递归升级成双参数，是处理「对比类」树问题的常用一招。