大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 28. 对称的二叉树。
题目汇总链接：https://www.algomooc.com/jianzhioffer
一、题目描述
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
限制：
- 0 <= 节点个数 <= 1000
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1、模拟
对称二叉树定义： 对于树中任意两个对称节点 L 和 R ，一定有：
- L.val = R.val：即此两对称节点值相等。
- L.left.val = R.right.val：即 L 的 左子节点 和 R 的 右子节点 对称；
- L.right.val = R.left.val：即 L 的 右子节点 和 R 的 左子节点 对称。
来源：Krahets
2、规律
从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树。
3、匹配
- 递归
4、边界
- 根节点为空
三、动画描述
隐藏内容
此处内容需要权限查看
会员免费查看四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
public boolean isSymmetric(TreeNode root) {
// 边界情况
if(root == null) return true;
// 递归判断左子树和右子树是否对称
return isSymmetriacalCor(root.left,root.right);
}
private boolean isSymmetriacalCor(TreeNode L,TreeNode R){
// 如果某根子树的左右两子树同时为空，肯定是对称的，直接返回 true
if(L == null && R == null){
return true;
}
// 说明根子树的左右两子树有某子树为空，某子树有值，不对称，返回 false
if(L == null || R == null){
return false;
}
// 左子树的值与右子树的值不相等，不对称，返回 false
if(L.val != R.val){
return false;
}
// 递归的对比当前节点的左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树是否对称
return isSymmetriacalCor(L.left,R.right) && isSymmetriacalCor(L.right,R.left);
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(N)。
空间复杂度
空间复杂度为 O(N)。
七、相关标签
- 树
