vvrf / DSA.log

问题拆解

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

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

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

递归比较镜像

public boolean isSymmetric(TreeNode root) {
    return root == null || mirror(root.left, root.right);
}

private boolean mirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val
        && mirror(a.left, b.right)
        && mirror(a.right, b.left);
}

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

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return mirror(root.Left, root.Right)
}

func mirror(a, b *TreeNode) bool {
    if a == nil && b == nil {
        return true
    }
    if a == nil || b == nil {
        return false
    }
    return a.Val == b.Val &&
        mirror(a.Left, b.Right) &&
        mirror(a.Right, b.Left)
}

pub fn is_symmetric(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    fn mirror(a: &Option<Rc<RefCell<TreeNode>>>, b: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        match (a, b) {
            (None, None) => true,
            (Some(a), Some(b)) => {
                let (a, b) = (a.borrow(), b.borrow());
                a.val == b.val && mirror(&a.left, &b.right) && mirror(&a.right, &b.left)
            }
            _ => false,
        }
    }
    root.map_or(true, |r| {
        let r = r.borrow();
        mirror(&r.left, &r.right)
    })
}

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

迭代版思路

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

复杂度

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

可以迁移的模式

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

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