前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 110. 平衡二叉树

Leetcode 110. 平衡二叉树

作者头像
zhipingChen
发布2019-05-24 09:46:51
3730
发布2019-05-24 09:46:51
举报
文章被收录于专栏:编程理解

题目描述

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

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

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

普通解法

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

代码语言:javascript
复制
# 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,并在每个递归函数结果处判断返回,避免后续所有的递归取高度值操作。

代码语言:javascript
复制
# 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
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.05.23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档