远程桌面登陆 Jmeter 服务注册中心 RabbitMQ events oauth dns autocomplete 河南普通话 easyui视频 网盘源码 广告投放系统源码 jquery循环遍历 jquery去掉空格 查看rabbitmq版本 java通用版qq浏览器下载 matlab求矩阵最大值 input取消边框 matlab输入参数太多 mysql学习 python搭建环境 python中文文档 python写入txt文件 python的安装路径 python零基础 java判断语句 java中tostring方法 linuxgrep linuxtail命令 怎么安装linux props 小米5c拆机 java语言程序设计 3389扫描器 编程语言实现模式 selinux关闭 惠普战99 小程序开发工具下载 spss20安装教程 圆角矩形工具改变弧度
当前位置: 首页 > 学习教程  > 编程语言

剑指 Offer 55 - II. 平衡二叉树 - leetcode 剑指offer系列

2020/8/11 18:45:31 文章标签:

题目难度: 简单

原题链接

今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了

题目描述

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。

  • 1 <= 树的结点个数 <= 10000

题目样例

示例

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。
给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

题目思考

  1. 可以只需要遍历一遍节点得到结果吗?

解决方案

思路

  • 有了昨天剑指 Offer 55 - I. 二叉树的深度 - leetcode 剑指 offer 系列的铺垫, 这道题相信大家都可以迎刃而解
  • 一个比较容易想到的思路是: 先计算出每个节点的深度, 并将其存入节点=>深度字典中; 然后再遍历一遍节点, 针对每个节点, 判断它左右子节点的深度是否满足要求, 所有节点都满足的话才说明平衡. 但是这种方案需要遍历两边节点, 效率不太高, 如何一次性遍历得出结果呢?
  • 回顾递归求深度的方案, 我们是先求得左右子树的深度, 然后才进一步得到当前节点的深度, 所以我们就可以直接加一个全局变量记录当前是否平衡, 并额外引入一个逻辑来比较子树深度, 如果不满足要求, 则直接把变量置为 false 直接返回即可
  • 注意本题并不适用于 BFS 迭代求深度的算法, 因为迭代方案求的是当前节点从上到下所在的层数, 每个节点并不知道自己的深度(从下往上, 从叶子节点到自身)究竟是多少, 所以无从判断是否平衡
  • 下面代码对必要的步骤有详细的解释, 方便大家理解

复杂度

  • 时间复杂度 O(N): 需要遍历整个树
  • 空间复杂度 O(H): H 表示树的高度, 也即递归的栈的消耗

代码

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # 递归, 边求深度边判断, 返回深度, 全局变量标记当前是否平衡
        balance = True

        def getDepth(node):
            nonlocal balance
            if not node or not balance:
                # 递归出口: 如果节点为空或者不平衡, 返回0, 无需继续递归了
                return 0
            ldepth = getDepth(node.left)
            rdepth = getDepth(node.right)
            if abs(ldepth - rdepth) > 1:
                # 不平衡, 全局变量设为false
                balance = False
            # 返回当前节点自身的深度
            return max(ldepth, rdepth) + 1

        getDepth(root)
        return balance

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊

每日精选算法题 - 微信扫一扫关注我


本文链接: http://www.dtmao.cc/news_show_100011.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?