温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

python中的平衡二叉树该怎么理解

发布时间:2021-12-13 15:46:24 来源:亿速云 阅读:161 作者:柒染 栏目:大数据

这期内容当中小编将会给大家带来有关python中的平衡二叉树该怎么理解,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。

题目描述

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 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
                           

上述就是小编为大家分享的python中的平衡二叉树该怎么理解了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI