专栏首页五分钟学算法两分钟弄懂对称二叉树

两分钟弄懂对称二叉树

大家好呀,我是吴师兄,今天照例来更新一道 LeetCode 算法题,根据以往数据来看,这类文章的打开率普遍不高,一般在三四千左右,远远低于水文或者热点文一两万的阅读量,一个合格的自媒体人正确的做法应该是抛弃前者不再更新这类技术文,我也曾经纠结彷徨过,到底是追逐阅读量还是放平心态写好技术文服务好读者

这种心态导致我有时候看到技术文阅读量、点赞量不佳会愤愤不平:MD,再也不写技术文了,可隔了一会看到一道算法题又忍不住想写出来分享。

反正挺难受的,直到前几天我看到了下面这段话。

思来想去,我觉得挺多读者关注我的公众号是想学一些技术的,所以还是保持每周更新一两道算法题解的频率,希望能日拱一卒,帮助读者在算法面试的时候能有印象:这道题目我在五分钟学算法见过!

所以喜欢看题解的读者记得星标一下公众号,五分钟学算法,让算法面试没那么难!

扯远了,来看今天的这道算法题。

这道题目的描述是这样子的:实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

题目很好理解,首先需要弄清楚对称的含义,它隐含了三层意思,即对于树中任意两个对称节点 L 和 R ,一定有:

1、L.val = R.val:即此两对称节点值相等。

2、L.left.val = R.right.val:即 L 的左子节点和 R 的右子节点对称。

3、 L.right.val = R.left.val:即 L 的右子节点和 R 的左子节点对称。

思路也就很简单了,我们可以从底至顶进行递归操作,判断每对节点是否对称,从而判断树是否为对称二叉树。

直接通过图片来看是怎么操作的。

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

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

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

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

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

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

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

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

代码如下,两分钟应该能写出来:

// 公众号:五分钟学算法
// 作者:程序员吴师兄

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);
    }
}

最后小小的总结一下,二叉树具备天然的递归性,往往在处理二叉树的题目时,我们都需要去思考怎么样利用递归,想清楚能解决 50% 的二叉树问题。

好了,今天的文章就到这里,我们下篇文章见,有收获记得点个赞,五分钟学算法,让算法面试没那么难!

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-07-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅谈多路查找树(B树)

    曾今我不知道多叉树有上面用,所以对于多叉树并没有过多的关注,或者说,基本没关注。 直到我了解到了多路查找树(B树),我知道,是我浅薄了。

    看、未来
  • 算法导论第十三章 红黑树(1)

    这一章真的把我害惨了,之前至少尝试看过3遍,每次看之前都下定决定一定要把它拿下,可是由于内容较多,深度够深,以致于每次要不是中途有什么事放弃了就跳过了,要不是花...

    范蠡
  • 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

    红黑树算是很难的一种数据结构吧,一般很少考察插入、删除等具体操作步骤,如果遇到要你手写红黑树的面试官,就直接告辞吧。所以,更多是会考察你对红黑树的理解程度,考察...

    乔戈里
  • TreeMap 源码分析

    TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 ...

    田小波
  • TreeMap 源码分析

    TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 ...

    田小波
  • 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

    红黑树算是很难的一种数据结构吧,一般很少考察插入、删除等具体操作步骤,如果遇到要你手写红黑树的面试官,就直接告辞吧。所以,更多是会考察你对红黑树的理解程度,考察...

    编程文青李狗蛋
  • 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 经典算法之二叉搜索树

    二叉树(Binary Tree)是一种特殊的树类型,其每个节点最多只能有两个子节点。这两个子节点分别称为当前节点的左孩子(left child)和右孩子(rig...

    用户3467126
  • python 实现二叉树的深度 & 广度优先遍历

    前面说到算法被虐了,这回我要好好把它啃下来。哪里跌倒就要从哪里站起来。这是我复习算法与数据结构时的小笔记,这里就 po 出来,给大家也复习一下旧的知识点,查缺补...

    小小詹同学
  • 用C语言建个单向链表

    Let life be beautiful like summer flowers and death like autumn leaves。生如夏花之灿烂,死...

    小Bob来啦
  • 学习数据结构的原因&方法 原

    wuweixiang
  • 图解!24张图彻底弄懂九大常见数据结构!

    数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊...

    cxuan
  • 程序员才看得明白的面试圣经

    除了直接申请面试以外,一般说来,还有两种途径来获得面试的机会:由现在的雇主推荐,或者通过LinkedIn。虽然前者会快一些、更尊敬一些,但后者很可能是大部分应聘...

    哲洛不闹
  • 算法导论第十三章 红黑树

      写在前面:这一章真的把我害惨了,之前至少尝试看过3遍,每次看之前都下定决定一定要把它拿下,可是由于内容较多,深度够深,以致于每次要不是中途有什么事放弃了就跳...

    猿大白
  • 聊聊整体性学习方法

    「整体性学习方法」是在一本叫做《如何高效学习》的书中看到的。这本书的作者是个老外,他用一年就学完了四年的麻省理工课程。而这本书正是其这一年来的学习心得,书中介绍...

    陈树义
  • 聊聊整体性学习方法

    「整体性学习方法」是在一本叫做《如何高效学习》的书中看到的。这本书的作者是个老外,他用一年就学完了四年的麻省理工课程。而这本书正是其这一年来的学习心得,书中介绍...

    范蠡
  • 【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

    例如,我现在想要查找数值为14的节点。由于二叉查找树的特性,我们可以很快着找到它,其过程如下:

    帅地
  • 如何有效的写算法题

    “龟系”刷法的精髓就是每个题目都做干净。不满足于一种解法,各种解法都写一写。这种流派适合不太急于准备算法面试的小伙伴,追求算法的干净优雅。

    五分钟学算法
  • 数据压缩的元老——哈夫曼树精解

    数据结构从逻辑结构上可以分为:集合、线性表、树、图 集合中常用的数据结构是背包等。 线性表包括栈、链表、队列等。 树包括堆、二叉树、哈夫曼树等。 图包括有...

    文彬

扫码关注云+社区

领取腾讯云代金券