Leetcode 110. 平衡二叉树

题目描述

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

普通解法

二叉树为高度平衡二叉树,则二叉树中以任意节点为根节点的子树皆为高度平衡二叉树。仿照后序遍历二叉树每个节点,若左子树和右子树皆为高度平衡二叉树,则进一步判断左子树与右子树高度差是否大于一即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        if not self.isBalanced(root.left) or not self.isBalanced(root.right):
            return False
        return abs(self.depth(root.left)-self.depth(root.right))<2
        
    def depth(self,root:TreeNode):
        if not root:
            return 0
        l=self.depth(root.left)
        r=self.depth(root.right)
        return max(l,r)+1

对于二叉树中高度不同的子二叉树,若其左子树和右子树均为高度平衡二叉树,则需要进一步计算左右子树的高度。即代码流程中存在多次计算子树高度的过程,存在重复的计算,造成性能浪费。

优化解法

观察上面代码中 depth 函数可知,获取二叉树根节点 root 的高度时,需要获取该二叉树中 root 节点以外的所有节点高度,此时自然知晓每个节点的左右子树高度差,即只需要一次计算根节点高度即可完成判断。

对上面代码中 depth 函数稍作改动,在正常的计算左右子树高度外,添加对左右子树高度的差值判断,若差值小于二,则正常执行;否则二叉树为非高度平衡二叉树,直接返回 -1,并在每个递归函数结果处判断返回,避免后续所有的递归取高度值操作。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券