对称二叉树 图解题解

这道题到底在问什么

树

1 →(2,2)，左2→(3,4)，右2→(4,3)

输出

true

先想最直接的笨办法

最直觉的想法：先复制整棵树、把每个节点的左右孩子翻转造出「镜像树」，再和原树一个一个比。能对，但要额外建一棵树、多走一遍，空间和代码都更重，纯属多此一举。（动画第 3 步）

最优解：一步一步想明白

1. 3最直觉的想法：先复制整棵树、把每个节点的左右孩子翻转造出「镜像树」，再和原树一个一个比。能对，但要额外建一棵树、多走一遍，空间和代码都更重，纯属多此一举。
2. 4转折：对称的本质是「左子树」和「右子树」互为镜像，不必真造出镜像树，让一个递归同时握住左 L、右 R 两个节点对照走即可。规则：都空就对称；一空一非就不对称；否则要求 L.val 等于 R.val，且 L 的左配 R 的右(外侧)、L 的右配 R 的左(内侧)。这题能这么做，是因为对称是「两两镜像位置」的局部判断，天然适合双节点同步递归。
3. 5isMirror(左2, 右2)根 1 自己不用比，直接拿它的左孩子 L 等于 2 和右孩子 R 等于 2 开镜像比较。两个都非空，先看值：2 == 2 通过。转折点：不去真造镜像树，而是就让这一个递归同时握住 L、R 往下走。
4. 6展开 L,R 的孩子L 等于 2、R 等于 2 值相等后，对称要求交叉地往下递归两对：外侧 是 L.left 配 R.right、内侧 是 L.right 配 R.left。这两对都成立，整支才算镜像。先看外侧。
5. 7isMirror(3, 3)第一对外侧：左孩子的左 (3) 配 右孩子的右 (3)——这是离中线最远的一对。注意是交叉取：左的 left 对右的 right。3 == 3 通过，且两边都是叶子，这一对镜像成立。
6. 8isMirror(4, 4)第二对内侧：左孩子的右 (4) 配 右孩子的左 (4)——靠近中线的一对，同样交叉取。4 == 4 通过。外侧、内侧两对都成立，左 2 和右 2 这一支镜像完全通过。
7. 9外✓ 内✓左 2 与右 2 这一支：值相等、外侧相等、内侧相等，三项都成立，isMirror(左2, 右2) 返回 True。这棵小树只有这一支要比，根的两个孩子镜像即整树镜像。
8. 10值 → 外侧 → 内侧把这一支慢放一遍，记住每次 isMirror 永远是三连：先比手里这两个节点的值(高亮的中层 2 和 2)，再交叉连外侧那对(最外的 3 和 3)，再交叉连内侧那对(中间的 4 和 4)。交叉就是「左的外 配 右的外」——连线总在中线两边镜像着走。
9. 11全部 ✓ → return True每一对镜像位置都相等，递归全程返回 True，整棵树对称。只要途中有一对不等或结构对不上，就会立刻短路返回 False。下面看看那种不对称的情况长什么样。
10. 12isMirror(9, 4)假设左孩子的右改成了 9。走到内侧这对：L.right=9 配 R.left=4，9 != 4 不成立。这一对镜像失败。注意外侧的 3 配 3 其实已经通过了，问题只出在内侧这一对。
11. 13不对称 → return False只要任意一对镜像位置不相等，不必再比其余节点，直接 return False——递归靠 and 短路，一处假则全假。回到正例：正因为每一对都相等，才返回 True。
12. 16判断对称、判断两树相同、合并两棵树，都用「同时握住两个节点往下递归」的双指针式 DFS。对称就交叉(左配右)、相同就平行(左配左)——只差递归传参那一处。
13. 21把这题练到能复述后，去 二叉树专题 里迁移：交叉换平行就是 LC100 相同的树、再套一层枚举子树就是 LC572 另一棵树的子树、把比较换成「拷贝/翻转」就是 LC226 翻转二叉树。卡壳就点右下角问小欧，或去通关训练里连刷这一串。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        def same(a, b):
            if not a and not b:
                return True
            if not a or not b:
                return False
            return a.val == b.val and same(a.left, b.right) and same(a.right, b.left)
        return same(root.left, root.right)

class Solution {
    bool same(TreeNode* a, TreeNode* b) {
        if (!a && !b) return true;
        if (!a || !b) return false;
        return a->val == b->val && same(a->left, b->right) && same(a->right, b->left);
    }
public:
    bool isSymmetric(TreeNode* root) { return !root || same(root->left, root->right); }
};

class Solution {
    boolean same(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        return a.val == b.val && same(a.left, b.right) && same(a.right, b.left);
    }
    public boolean isSymmetric(TreeNode root) { return root == null || same(root.left, root.right); }
}

def dfs(a, b):
    if not a and not b: return True   # 1) 两个都空 → 这对到底了，算过
    if not a or not b:  return False  # 2) 一空一非 → 结构都不一致，直接否
    if a.val != b.val:  return False  # 3) 值不等 → 否
    # 4) 递归两对子节点 —— 只有这一行决定你在做哪道题:
    return dfs(a.?, b.?) and dfs(a.?, b.?)
    #   对称(LC101): dfs(a.left, b.right) and dfs(a.right, b.left)   ← 交叉
    #   相同(LC100): dfs(a.left, b.left)  and dfs(a.right, b.right)  ← 平行

bool dfs(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;        // 两个都空
    if (!a || !b) return false;       // 一空一非
    if (a->val != b->val) return false;
    // 这一行决定题型:
    return dfs(a->?, b->?) && dfs(a->?, b->?);
    //  对称: a->left,b->right  &&  a->right,b->left  (交叉)
    //  相同: a->left,b->left   &&  a->right,b->right (平行)
}

boolean dfs(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;   // 两个都空
    if (a == null || b == null) return false;  // 一空一非
    if (a.val != b.val) return false;
    // 这一行决定题型:
    return dfs(a.?, b.?) && dfs(a.?, b.?);
    //  对称: a.left,b.right  &&  a.right,b.left  (交叉)
    //  相同: a.left,b.left   &&  a.right,b.right (平行)
}

复杂度

面试官可能追问