代码编织梦想

平衡二叉树

难度:简单

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1:

请添加图片描述

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

请添加图片描述

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例 3:

输入:root = []
输出:true

自底向上的递归

思路:

自底向上递归的做法类似于后序遍历,对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 − 1 −1 1。如果存在一棵子树不平衡,则整个二叉树一定不平衡。

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树中的节点个数。使用自底向上的递归,每个节点的计算高度和判断是否平衡都只需要处理一次,最坏情况下需要遍历二叉树中的所有节点,因此时间复杂度是 O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过 n n n
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def recursion(node):
            if node is None:
                return 0
            l_deep = recursion(node.left)
            r_deep = recursion(node.right)
            if l_deep == -1 or r_deep == -1 or abs(l_deep - r_deep) > 1:
                return -1
            return max(l_deep, r_deep) + 1
        return recursion(root) != -1

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/balanced-binary-tree

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45616285/article/details/128670991

漫画:二叉树系列 第三讲(BST与其验证)-爱代码爱编程

在上一节中,我们分别学习了DFS与BFS。在本节中,我们将继续学习一种特殊的二叉树结构 —— 二叉搜索树(BST)。 01 二叉搜索树 先看定义:二叉搜索树(Binary Search Tree),(又:二叉查找树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值

《算法和数据结构》学习路线指引-爱代码爱编程

本文已收录于专栏 🌳《画解数据结构》🌳 🙉饭不食,水不饮,题必须刷🙉 C语言免费动漫教程,和我一起打卡! 🌞《光天化日学C语言》🌞 LeetCode 太难?先看简单题! 🧡《C语言入门100例》🧡 数据结构难?不存在的! 🌳《画解数据结构》🌳

《算法和数据结构》题海战术篇-爱代码爱编程

文章目录 1️⃣前言:追忆我的刷题经历2️⃣算法和数据结构的重要性👪1、适用人群🎾2、有何作用📜3、算法简介🌲4、数据结构3️⃣如何开始持续的刷题📑1、立军令状👩‍❤️‍👩2、培养兴趣🚿3、狂切水题💪🏻4、养成习惯🈵5、一周出师4️⃣简单数据结构的掌握🚂1、数组🎫2、字符串🎇3、链表🌝4、哈希表👨‍👩‍👧5、队列👩‍👩‍👦‍👦6、栈🌵7、二叉树

《算法和数据结构》从语言到算法的过渡篇-爱代码爱编程

本文已收录于专栏 💜《夜深人静写算法》💜 前言   看到太多爆肝熬夜整合的内容,又是几万字,又是爆肝,我也来试试看能不能扛得住。试完后发现,果然还是扛不住啊。但是既然整理完了,那就把我的 算法学习路线 发出来吧,我把整个算法学习的阶段总结成了五个步骤,分别为: 「 基础语法 」、 「 语法练习 」、 「 数据结构 」、 「 算法入门 」

【万人千题】《第一阶段:算法零基础抱团打卡》学习路线指引-爱代码爱编程

  博主会带领大家首先进行《算法零基础100讲》的训练,每天把一些知识点巩固后做完相应练习题,和群友一起打卡,今天是打卡 第三天。具体玩法本文会进行详细介绍。 打卡地址 社区:万人千题 前言   本文会介绍学习算法的主要学习路线,大致分为以下几个步骤:   而 万人千题计划 从第三个内容开始,前两个内容会通过算法学习的过程中不断巩固

「 英雄哪里出来 」算法博客阅读指引-爱代码爱编程

文章目录 前言一、语言基础1、「 光天化日学C语言 」二、刷题必读1、「 LeetCode零基础指南 」2、「 九日集训每日打卡 」三、语言入门1、「 C语言入门100例 」2、「 C语言每日打卡 」四、算法入门1、「 算法零基础100讲 」2、「 算法零基础每日打卡 」五、算法进阶1、「 画解数据结构 」2、「 算法进阶50讲 」3、「 Leet

《算法和数据结构》初出茅庐篇-爱代码爱编程

🧧2022 "算法" 赛道新星计划导师🧧 下滑到文末报名 文章目录 前言一、刷提前的准备1、编程语言2、编程环境3、测试用例二、推荐的书1、LeetCode零基础指南2、算法导论三、零基础如何刷LeetCode1、水题2、多维思考3、举一反三4、参加九日集训四、如何学习算法1、系统整理2、解题划级五、零基础算法十题入门1

算法如何学习?别想太多,两个字-爱代码爱编程

文章目录 前言一、语言基础1、「 光天化日学C语言 」二、刷题必读1、「 LeetCode零基础指南 」2、「 九日集训每日打卡 」三、语言入门1、「 C语言入门100例 」四、算法入门1、「 算法零基础100讲 」五、算法进阶1、「 画解数据结构 」2、「 LeetCode算法题集汇总 」3、「 夜深人静写算法 」六、社区活动1、「 明年今日 」

学算法先学数据结构?是否是无稽之谈?-爱代码爱编程

前言   「 数据结构 」 和 「 算法 」 是密不可分的,两者往往是「 相辅相成 」的存在,所以,在学习 「 数据结构 」 的过程中,不免会遇到各种「 算法 」。  到底是先学 数据结构 ,还是先学 算法,我认为不必纠结这个问题,一定是一起学的。  数据结构 常用的操作一般为:「 增 」「 删 」「 改 」「 查 」。基本上所有的数据结构都是围绕

算法怎么学?每天早起刷题,坚持一定会有收获-爱代码爱编程

文章目录 前言一、语言基础1、「 光天化日学C语言 」二、刷题必读1、「 LeetCode零基础指南 」2、「 九日集训每日打卡 」三、语言入门1、「 C语言入门100例 」四、算法入门1、「 算法零基础100讲 」五、算法进阶1、「 画解数据结构 」2、「 LeetCode算法题集汇总 」3、「 夜深人静写算法 」 前言   很多人看

【xsong说算法】剑指offer一个月打卡完毕-爱代码爱编程

手把手带你刷剑指Offer 前言   该文章刷剑指offer 的方式不是按照题的顺序去刷的,而是在LeetCode 上有一个剑指offer 的学习计划,我是按照那个计划刷的。这个计划总结的比较系统,给我们分好类了,刷起来比较舒服,一个月的学习计划,大家一定要坚持刷完! 第一天 栈与队列(简单)2022/2/26 题目题解链接剑指 Offer 09.

【LeetCode】-二叉树-爱代码爱编程

文章目录 前言一、二叉树的层序遍历二、 翻转二叉树三、 对称二叉树四、 二叉树的最大深度五、 二叉树的最小深度六、 二叉树的最小深度七、 平衡二叉树八、二叉树的层序遍历九、二叉树的所有路径十、左叶子之和十一、找树左下角的值十二、路径总和十三、路径总和 II十四、最大二叉树十五、合并二叉树十六、二叉搜索树中的搜索十七、验证二叉搜索树十八、二叉搜索树的

英雄算法联盟---五月集训总结_...1999的博客-爱代码爱编程

目录 1. 知识星球英雄算法联盟2.训练历程与感悟3.加入星球的变化4.未来目标5.结尾tips:想加入星球的小伙伴可以扫描下方的二维码,加入星球后可以找我返现! 1. 知识星球英雄算法联盟 英雄算法联盟知识星球链接 2.训练历程与感悟 第一天:数组 第二天:字符串 第三天:排序 第四天:贪心 第五天:双指针 第六天:滑动窗口 第七天:哈

《六月集训》第十五天——深度优先搜索_xiucai11的博客-爱代码爱编程

文章目录 前言💎一、题目一🏆1.题目描述🏆2.解题思路🏆3.代码详解💎二、题目二🏆1.题目描述🏆2.解题思路🏆3.代码详解💎三、星球推荐 前言         刷题坚持每一天,以下题目引用自:力扣(LeetCode) 💎一、题目一 🏆1.题目描述 原题链接:508. 出现次数最多的子树元素和 给你一个二叉树的根结点 root ,

《六月集训》第十八天——树_xiucai11的博客-爱代码爱编程

文章目录 前言💎一、题目一🏆1.题目描述🏆2.解题思路🏆3.代码详解💎二、题目二🏆1.题目描述🏆2.解题思路🏆3.代码详解💎三、星球推荐 前言         刷题坚持每一天,以下题目引用自:力扣(LeetCode) 💎一、题目一 🏆1.题目描述 原题链接:link 二叉树上有 n 个节点,按从 0 到 n - 1 编号,其中节

六月集训(19)二叉树_爱吃烤秋刀鱼的博客-爱代码爱编程

文章目录 1.LeetCode:331. 验证二叉树的前序序列化2.LeetCode:297. 二叉树的序列化与反序列化3.剑指 Offer II 048. 序列化与反序列化二叉树4.剑指 Offer 37. 序列化二叉树 1.LeetCode:331. 验证二叉树的前序序列化 原题链接         序列化二叉树的一种方法是使用

《六月集训》第十九天——二叉树_xiucai11的博客-爱代码爱编程

文章目录 前言💎一、题目一🏆1.题目描述🏆2.解题思路🏆3.代码详解💎二、题目二🏆1.题目描述🏆2.解题思路🏆3.代码详解💎三、星球推荐 前言         刷题坚持每一天,以下题目引用自:力扣(LeetCode) 💎一、题目一 🏆1.题目描述 原题链接:331. 验证二叉树的前序序列化 序列化二叉树的一种方法是使用 前序遍历

《六月集训》第二十天——二叉搜索树_xiucai11的博客-爱代码爱编程

文章目录 前言💎一、题目一🏆1.题目描述🏆2.解题思路🏆3.代码详解💎二、题目二🏆1.题目描述🏆2.解题思路🏆3.代码详解💎三、题目三🏆1.题目描述🏆2.解题思路🏆3.代码详解💎四、题目四🏆1.题目描述🏆2.解题思路🏆3.代码详解💎五、星球推荐 前言         刷题坚持每一天,以下题目引用自:力扣(LeetCode) 💎一、题目一