E-110. Balanced Binary Tree

Loading...LeetCode

👏🏻 Python - Tree高度延伸的一类题目 公瑾™

关于上述连接中说第一个暴力算法的复杂度是O(nlogn), 应该是错的(待验证). 我认为复杂度应该是O(n^2)

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        right=self.get_height(root.right)
        left=self.get_height(root.left)
        if abs(right-left)>1:
            return False
        else:
            return self.isBalanced(root.right) and self.isBalanced(root.left) 
        
    def get_height(self, root):
        if not root:
            return 0
        right=self.get_height(root.right)
        left=self.get_height(root.left)
        return max(right,left)+1

O(n)写法:

'''
相当于是个自底向上的比较, 这样比较一遍就能知道整棵树有没有node的左右子树高度差>1了.
'''
class Solution(object):
    def isBalanced(self, root):
        if not root: 
            return True
        flag=[True]    #  <- 注意这里比较tricky的写法, 也可以写一个__init__把flag在里面初始化
        self.get_height(root, flag)
        return flag[0]

        
    def get_height(self, root, flag):
        if not root: 
            return 0
        left = self.get_height(root.left, flag)
        right = self.get_height(root.right, flag)
        if abs(left-right)>1:
            flag[0]=False
        return max(left,right)+1