对称二叉树

题目描述

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

示例

示例 1：

输入: root = [1, 2, 2, 3, 4, 4, 3]

      1
     / \
    2   2
   / \ / \
  3  4 4  3

输出: true

示例 2：

输入: root = [1, 2, 2, null, 3, null, 3]

      1
     / \
    2   2
     \   \
      3   3

输出: false

示例 3：

输入: root = []
输出: true

示例 4：

输入: root = [1]
输出: true

解题思路

判断一棵树是否对称，可以转化为判断它的左右子树是否镜像。

两颗子树互为镜像的条件：

1. 它们的根节点值相等。
2. 左子树的左子树与右子树的右子树互为镜像。
3. 左子树的右子树与右子树的左子树互为镜像。

使用双指针递归：一个指针遍历左子树（左→右），另一个指针遍历右子树（右→左），同时比较对应节点的值是否相等。

代码实现

/**
 * 对称二叉树 — DFS 双指针递归
 * @param {TreeNode} root - 二叉树根节点
 * @returns {boolean} 是否对称
 */
function isSymmetric(root) {
    if (!root) return true;

    const isMirror = (leftNode, rightNode) => {
        if (!leftNode && !rightNode) return true;
        if (!leftNode || !rightNode) return false;
        if (leftNode.val !== rightNode.val) return false;
        return isMirror(leftNode.left, rightNode.right)
            && isMirror(leftNode.right, rightNode.left);
    };

    return isMirror(root.left, root.right);
}

复杂度分析

• 时间复杂度：O(n)，遍历所有节点。
• 空间复杂度：O(h)，递归栈深度为树的高度，最坏情况 O(n)。

root = [1,2,2,3,4,4,3]

true