101. 对称二叉树

101. 对称二叉树

简单

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数目在范围[1, 1000]内
• -100 <= Node.val <= 100

📝 核心笔记：对称二叉树 (Symmetric Tree)

1. 核心思想 (一句话总结)

“照镜子：左子树的左手，必须等于右子树的右手；左子树的右手，必须等于右子树的左手。”我们要比较的不是一个节点的左右孩子，而是根节点的左子树和根节点的右子树这两棵独立的树。

• 外侧对比 (Outer)：左树的左 (p.left) vs 右树的右 (q.right)。
• 内侧对比 (Inner)：左树的右 (p.right) vs 右树的左 (q.left)。

2. 算法流程 (递归三部曲)

我们将根节点的左右子树拆开，分别称为p和q。

1. 终止条件 (Base Case)：

• • 都为空：p == null && q == null-> 对称 (True)。
  • 一个空一个不空：不对称 (False)。
  • (这部分逻辑在您的p == q中完美涵盖了)

1. 值比较：

• • p.val != q.val-> 不对称 (False)。

1. 递归 (Cross Check)：

• • isMirror(p.left, q.right)且isMirror(p.right, q.left)。
  • 只有两个方向都对称，整体才对称。

🔍 代码回忆清单

// 题目：LC 101. Symmetric Tree class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) return true; // 从根节点开始，拆分成左右两棵树进行比较 return isMirror(root.left, root.right); } // 这是一个改造版的 "isSameTree" // 实际上它检查的是 p 和 q 是否互为镜像 private boolean isMirror(TreeNode p, TreeNode q) { // 1. 终止条件：处理 null 的情况 if (p == null || q == null) { return p == q; // 只有两个都为 null 才返回 true } // 2. 核心递归： // A. 根节点值必须相同 // B. p 的左边 vs q 的右边 (外侧) // C. p 的右边 vs q 的左边 (内侧) return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left); } }

⚡ 快速复习 CheckList (易错点 & 迭代法)

• [ ]不要比较root.left和root.right！

• • 在递归函数内部，不要写if (p.left.val == p.right.val)。
  • 每一层只负责比较传入的p和q这两个节点，子节点的比较交给下一层递归。

• [ ]函数命名小建议

• • 虽然逻辑类似isSameTree，但为了避免歧义，建议 helper 函数命名为check或isMirror。因为SameTree通常暗示left比left，而这里是left比right。

• [ ]迭代法怎么写？(面试常见追问)

• • 使用队列 (Queue)。
  • 每次把u.left和v.right成对放入队列，再把u.right和v.left成对放入。
  • 每次取两个出来比对。如果队列空了都没报错，那就是对称的。

🖼️ 数字演练

树结构：

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

1. Start: CompareL(2)vsR(2).

• • Vals match (2==2).

1. Recurse Outer: CompareL.left(3)vsR.right(3).

• • Match!

1. Recurse Inner: CompareL.right(4)vsR.left(4).

• • Match!

1. Result: True.