leetcode with python:110. Balanced Binary Tree

题目:

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

给定一个binary tree,判断它是否为高度平衡二元树

在上题我们已经知道高度平衡二元树的定义是所有两子树高度最多相差1的binary tree
在写这题时我本来有个想法,但我想了很久还是无法实践
最后我还是直接用定义解去解QQ
不过当我在逛讨论区时发现有人将我原初的想法成功实践,不过待会再提
先看我用定义的解法

# 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 = rightclass Solution:    def isBalanced(self, root: Optional[TreeNode]) -> bool:        if not root:            return True                    def depth(root):             if not root:                return 0            return max(depth(root.left),depth(root.right))+1                if abs(depth(root.right)-depth(root.left))<=1:            return self.isBalanced(root.right) and self.isBalanced(root.left)        else:            return False

这里偷了104.写出的函数来用
透过递迴不断往下侦测各节点的左右子树高度相差是否超过1
一旦有出现差超过1的状况就回传False
最后执行时间61ms(faster than 80.27%)

其实我最初的想法是想改造104.测最大深度的函数
当比两侧子树大小时顺便侦测高度相差是否超过1
但我无法写出何时该回传高度何时该回传布林值的判断式,所以最后放弃了这个想法
而我在讨论区看到的实作出来的人是这样写的

# 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 = rightclass Solution:    def isBalanced(self, root: Optional[TreeNode]) -> bool:        def ans(root):            if root:                l=ans(root.left)                r=ans(root.right)                if l!=-1 and r!=-1 and abs(l-r)<=1:                    return max(l,r)+1                return -1            else:                return 0        return ans(root)!=-1

一旦发现高度相差超过1的情形,就让测最大深度函式的最终回传值变为-1
最后只要看结果是否等于-1就知道该树是否是高度平衡二元树了
挺巧妙的,是我当初没想到的办法
最后执行时间48ms(faster than 97.02%)

那我们下题见