101. 对称二叉树
题目描述
输入二叉树的根节点 root。二叉树按层序写成数组，空位置用 null 表示，例如 [3,9,20,null,null,15,7]。
判断这棵树是否左右对称：把它沿过根节点的竖直线翻转后，形状和各位置的值都与原树一致。
对称返回 true，否则返回 false。
示例 1
输入：root = [1,2,2,3,4,4,3] 输出：true
解释：左子树 2,3,4 与右子树 2,4,3 互为镜像。
示例 2
输入：root = [1,2,2,null,3,null,3] 输出：false
解释：两个 3 都是右孩子，镜像后位置对不上。
数据范围
- 节点数在
[1, 1000]范围内。 -100 <= Node.val <= 100
进阶：能否分别用递归和迭代两种方式实现？
解题思路：递归（镜像比较）
成对递归比较镜像节点：左的左对右的右，左的右对右的左。
为什么正确
mirror(a,b) 返回两棵子树是否互为镜像。
复杂度分析
时间 O(n)，递归栈 O(h)；h 为树高，最坏可为 n；Python 递归受解释器递归深度限制，深链树应改用显式栈。
易错点
必须交叉比较左右孩子；仅比较每层的值不足以保证结构对称。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isSymmetric(self, root):
def mirror(a, b):
if a is None or b is None:
return a is b
return (a.val == b.val and
mirror(a.left, b.right) and
mirror(a.right, b.left))
return root is None or mirror(root.left, root.right)class Solution {
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 a == b;
return (a.val == b.val &&
mirror(a.left, b.right) &&
mirror(a.right, b.left));
}
}class Solution {
public:
bool isSymmetric(TreeNode* root) {
return root == nullptr || mirror(root->left, root->right);
}
bool mirror(TreeNode* a, TreeNode* b) {
if (a == nullptr || b == nullptr)
return a == b;
return (a->val == b->val &&
mirror(a->left, b->right) &&
mirror(a->right, b->left));
}
};func isSymmetric(root *TreeNode) bool {
var mirror func(a, b *TreeNode) bool
mirror = func(a, b *TreeNode) bool {
if a == nil || b == nil {
return a == b
}
return a.Val == b.Val &&
mirror(a.Left, b.Right) &&
mirror(a.Right, b.Left)
}
return root == nil || mirror(root.Left, root.Right)
}var isSymmetric = function(root) {
const mirror = (a, b) => {
if (!a || !b)
return a === b;
return (a.val === b.val &&
mirror(a.left, b.right) &&
mirror(a.right, b.left));
};
return !root || mirror(root.left, root.right);
};function isSymmetric(root: TreeNode | null): boolean {
const mirror = (a: TreeNode | null, b: TreeNode | null): boolean => {
if (!a || !b)
return a === b;
return (a.val === b.val &&
mirror(a.left, b.right) &&
mirror(a.right, b.left));
};
return !root || mirror(root.left, root.right);
}其他解法
递归和迭代的配对规则完全相同：外侧比外侧、内侧比内侧。递归更简洁；迭代用队列代替调用栈，不会因递归过深而溢出。
解法 2：迭代（队列成对比较） 时间 O(n)，空间 O(n)
把递归改成队列。队列里每次放一对应该互为镜像的节点，初始为 (根的左孩子, 根的右孩子)。取出一对后：都为空就跳过；一个为空或值不同就不对称；否则把“外侧配外侧”(a.left, b.right) 和“内侧配内侧”(a.right, b.left) 两对入队。
避免了递归调用栈，适合深树。代码比递归略长，关键是入队时的配对顺序不能写错。
from collections import deque
class Solution:
def isSymmetric(self, root):
if root is None:
return True
queue = deque([(root.left, root.right)])
while queue:
a, b = queue.popleft()
if not a and not b:
continue
if not a or not b or a.val != b.val:
return False
# 外侧与外侧配对，内侧与内侧配对
queue.append((a.left, b.right))
queue.append((a.right, b.left))
return Trueclass Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> qu = new LinkedList<>();
qu.offer(root.left);
qu.offer(root.right);
while (!qu.isEmpty()) {
TreeNode a = qu.poll(), b = qu.poll();
if (a == null && b == null) continue;
if (a == null || b == null || a.val != b.val) return false;
qu.offer(a.left);
qu.offer(b.right);
qu.offer(a.right);
qu.offer(b.left);
}
return true;
}
}class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
queue<pair<TreeNode*, TreeNode*>> qu;
qu.push({root->left, root->right});
while (!qu.empty()) {
auto [a, b] = qu.front();
qu.pop();
if (!a && !b) continue;
if (!a || !b || a->val != b->val) return false;
qu.push({a->left, b->right});
qu.push({a->right, b->left});
}
return true;
}
};func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
queue := [][2]*TreeNode{{root.Left, root.Right}}
for len(queue) > 0 {
a, b := queue[0][0], queue[0][1]
queue = queue[1:]
if a == nil && b == nil {
continue
}
if a == nil || b == nil || a.Val != b.Val {
return false
}
queue = append(queue, [2]*TreeNode{a.Left, b.Right}, [2]*TreeNode{a.Right, b.Left})
}
return true
}var isSymmetric = function(root) {
if (!root) return true;
const queue = [[root.left, root.right]];
let head = 0;
while (head < queue.length) {
const [a, b] = queue[head++];
if (!a && !b) continue;
if (!a || !b || a.val !== b.val) return false;
queue.push([a.left, b.right], [a.right, b.left]);
}
return true;
};function isSymmetric(root: TreeNode | null): boolean {
if (!root) return true;
const queue: [TreeNode | null, TreeNode | null][] = [[root.left, root.right]];
let head = 0;
while (head < queue.length) {
const [a, b] = queue[head++];
if (!a && !b) continue;
if (!a || !b || a.val !== b.val) return false;
queue.push([a.left, b.right], [a.right, b.left]);
}
return true;
}