大家好,我是程序员吴师兄,欢迎来到 图解剑指 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、边界

  • 根节点为空

三、动画描述

隐藏内容
  • 普通用户购买价格:5积分
  • 会员用户购买价格:免费
  • 永久会员用户购买价格:免费推荐

四、图片描述

剑指 Offer 28. 对称的二叉树.002

剑指 Offer 28. 对称的二叉树.003

剑指 Offer 28. 对称的二叉树.004

剑指 Offer 28. 对称的二叉树.005

剑指 Offer 28. 对称的二叉树.006

剑指 Offer 28. 对称的二叉树.007

剑指 Offer 28. 对称的二叉树.008

剑指 Offer 28. 对称的二叉树.009

五、参考代码

// 登录 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)。

七、相关标签

发表评论

邮箱地址不会被公开。 必填项已用*标注