0101.对称二叉树

难度：🟢 简单

标签：树、深度优先搜索、广度优先搜索、二叉树

链接：101. 对称二叉树

题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

解题思路

核心思想

本题的核心是判断一棵树是否是其自身的镜像。一棵树是轴对称的，当且仅当：

1. 它的根节点的左子树与右子树是镜像对称的。

2. 对于任意两棵镜像对称的树 T1 和 T2，必须满足：

   • 它们的根节点值相等。

   • T1 的左子树与 T2 的右子树是镜像对称的。

   • T1 的右子树与 T2 的左子树是镜像对称的。

思路选择

递归法 是解决此问题最自然、最清晰的思路。我们可以定义一个辅助递归函数，比如 isMirror(node1, node2)，其功能是判断两棵树 node1 和 node2 是否互为镜像。然后，我们用这个函数来判断根节点的左子树和右子树是否互为镜像。

关键步骤

1. 主函数入口：isSymmetric 函数是主入口。如果根节点 root 为空，它本身是对称的，返回 true。否则，调用辅助函数 isMirror(root.left, root.right) 来判断其左右子树是否对称。

2. 定义辅助函数 isMirror(node1, node2)： a. 终止条件 1：如果 node1 和 node2 都为 null，说明这对称位置上的子树都为空，它们是镜像对称的，返回 true。 b. 终止条件 2：如果 node1 和 node2 中只有一个为 null，或者它们的值不相等，那么它们必然不是镜像对称的，返回 false。 c. 递归分解：如果以上条件都不满足，说明两个节点都存在且值相等。我们需要继续递归地比较它们的子树。根据镜像对称的定义，需要比较 node1.left 和 node2.right，以及 node1.right 和 node2.left。只有这两对子树都互为镜像时，node1 和 node2 才互为镜像。

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 辅助函数：判断两棵树是否互为镜像
 * @param {TreeNode} node1
 * @param {TreeNode} node2
 * @return {boolean}
 */
var isMirror = function (node1, node2) {
    // 如果两个节点都为空，则对称
    if (node1 === null && node2 === null) return true;
    // 如果只有一个为空，或节点值不同，则不对称
    if (node1 === null || node2 === null || node1.val !== node2.val) return false;

    // 递归地比较：左子树的左边 vs 右子树的右边 和 左子树的右边 vs 右子树的左边
    return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    if(root === null) return true;
    // 判断根节点的左右子树是否互为镜像
    return isMirror(root.left, root.right);
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是树的节点总数。我们最多需要遍历树中的每一个节点一次。

• 空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。在最坏情况下（树退化为一条链），空间复杂度为 O(n)；在最好的情况下（一个完全平衡的树），空间复杂度为 O(log n)。

相关题目

• 0100.相同的树

• 0572.另一棵树的子树

总结

本题是考察二叉树递归遍历的经典题目。其解题的精髓在于正确地定义递归函数的含义，并将其分解为对称的子问题。通过比较 node1.left 与 node2.right 以及 node1.right 与 node2.left，巧妙地实现了“镜像”的判断。