剑指 Offer 28. 对称的二叉树

大家好，我是程序员吴师兄，欢迎来到 图解剑指 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)。

七、相关标签

• 树

程序员吴师兄算法训练营永久会员

收藏 海报 链接