.jpg)
548 字
3 分钟
对称二叉树
.png)
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
解题思路
- 递归镜像比较：
- 定义辅助函数比较两棵树（left 和 right）是否对称
- 终止条件：
- 两节点都为空 → 对称
- 一空一非空 → 不对称
- 节点值不同 → 不对称
- 递归比较：
left.left与right.rightleft.right与right.left
- 迭代队列法：
- 使用队列存储需比较的节点对
- 初始入队根节点的左右子节点
- 每次出队两个节点比较：
- 若不对称立即返回 false
- 否则将子节点按镜像顺序入队
关键洞察
- 镜像递归原理：
- 对称 = 左子树与右子树镜像相同
- 递归方向对称（左←→右，右←→左）
- 成对处理逻辑：
- 迭代法需成对入队节点
- 比较顺序：
(A.left, B.right)和(A.right, B.left)
- 空节点处理：
- 空节点需要参与比较
- 仅当两节点都为空才视为对称
- 根节点特殊处理：
- 空树视为对称
- 单节点树视为对称
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归法 | O(n) | O(h) [树高, 最坏O(n)] |
| 迭代法 | O(n) | O(w) [最大宽度] |
注：n 为节点总数，h 为树高度，w 为树最大宽度
代码实现
递归法
/** * 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} root * @return {boolean} */const isSymmetric = (root) => { if (!root) return true;
const compare = (left, right) => { // 双空：对称 if (!left && !right) return true; // 单空 或 值不同：不对称 if (!left || !right || left.val !== right.val) return false; // 递归比较镜像节点 return compare(left.left, right.right) && compare(left.right, right.left); };
return compare(root.left, root.right);};迭代法
/** * 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} root * @return {boolean} */var isSymmetric = function (root) { if (!root) return true; const queue = [root.left, root.right]; while (queue.length) { const u = queue.pop(); const v = queue.pop(); if (!u && !v) continue; if (!u || !v || u.val !== v.val) return false; queue.unshift( u.left, v.right, u.right, v.left ) } return true;};相似题目
- 无