• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

110. Balanced Binary Tree(平衡树判断)

leetcode admin 8个月前 (03-27) 328次浏览 0个评论 扫描二维码

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

 

解法:

104. Maximum Depth of Binary Tree

最基础的递归,先递归到底,当 Leaf Node 的左右两个 Children Node 都分别触及 Base Case,也就是 None 的时候,向上返回。然后之后对应当前 node,左右两边的递归都操作结束以后,返回的过程中对左右高度进行对比,取两个中间最大值,然后这里记住要加1,也就是当前的层数。

class Solution(object):
    def maxDepth_gd(self, root):
        '''bugfree'''
        if not root: return 0

        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

有了 104 的基础,我们在延伸下看看 110 这道题,其实就是基于高度计算,然后判断一下。

但由于嵌套的 Recursion 调用,整体的时间复杂度是:O(nlogn) , 在每一层调用 get_height 的平均时间复杂度是 O(N),然后基于二叉树的性质,调用了的高度是 logn,所以 n * logn 的时间复杂。

时间复杂度为什么是 nlogn 搞不清楚的看 时间复杂度图解

class Solution(object):
    def isBalanced(self, root):
        if not root: return True
        left = self.get_height(root.left)
        right = self.get_height(root.right)
        if abs(left - right) > 1: 
            return False  
        return self.isBalanced(root.left) and self.isBalanced(root.right)

        
    def get_height(self, root):
        if not root: return 0
        left = self.get_height(root.left)
        right = self.get_height(root.right)
        return max(left, right) + 1

上面这种 Brute Froce 的方法,整棵树有很多冗余无意义的遍历,其实我们在处理完get_height这个高度的时候,我们完全可以在检查每个节点高度并且返回的同时,记录左右差是否已经超过 1,只要有一个节点超过 1,那么直接返回 False 即可,因此我们只需要在外围设立一个全球变量记录 True 和 False,在调用 get_height 的时候,内置代码里加入对左右高度的判定即可,代码如下

时间复杂度: O(N)

# Recursive Rules:
# 索取:Node 的左孩子是不是全部是 Balanced,Node 的右孩子是不是全部是 Balanced 的,
# 返回:如果都是 Balanced 的,返回 True,不然返回 False

class Solution(object):
    def isBalanced(self, root):
        self.flag = False
        self.getHeight(root)
        return not self.flag
        
    
    def getHeight(self, root):
        if not root: return 0
        left = self.getHeight(root.left)
        right = self.getHeight(root.right)
        if abs(left - right) > 1: 
            self.flag = True
        return max(left, right) + 1

Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明110. Balanced Binary Tree(平衡树判断)
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!