【LintCode 简单】93. 平衡二叉树

男娘i 2022-06-01 04:49 162阅读 0赞

1.问题描述：

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。

2.样例：

给出二叉树 A=`{3,9,20,#,#,15,7}`, B=`{3,#,20,15,7}`

A)  3            B)    3 
       / \                  \
      9  20                 20
        /  \                / \
       15   7              15  7

二叉树A是高度平衡的二叉树，但是B不是。

3.代码：

"""
    Definition of TreeNode:
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.left, self.right = None, None
    """
    
    
    class Solution:
        """
        @param: root: The root of binary tree.
        @return: True if this Binary tree is Balanced, or false.
        """
        def isBalanced(self, root):
            # write your code here
            if root is None:
                return True
            a=self.treeHeight(root.left)
            b=self.treeHeight(root.right)
            if abs(a-b)>1:
                return False
            else:
                return self.isBalanced(root.left) and self.isBalanced(root.right)
                
        def treeHeight(self,root):
            if root is None:
                return 0
            else:
                lheight=self.treeHeight(root.left)
                rheight=self.treeHeight(root.right)
            return max(lheight,rheight)+1

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关【LintCode 简单】93. 平衡二叉树

1.问题描述：给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。 2.样

男娘i/ 2022年06月01日 04:49/ 0 赞/ 163 阅读

相关【LintCode 简单】375. 克隆二叉树

1.问题描述：深度复制一个二叉树。给定一个二叉树，返回一个他的克隆品。 2.样例：给定一个二叉树： 1 / \ 2 3 / \ 4 5 返回

柔情只为你懂/ 2022年06月01日 01:05/ 0 赞/ 144 阅读

相关【LintCode 简单】469. 等价二叉树

1.问题描述：检查两棵二叉树是否等价。等价的意思是说，首先两棵二叉树必须拥有相同的结构，并且每个对应位置上的节点上的数都相等。 2.样例： 1

电玩女神/ 2022年06月01日 01:05/ 0 赞/ 128 阅读

相关【LintCode 简单】175. 翻转二叉树

1.问题描述：翻转一棵二叉树。 2.样例： 1 1 / \ / \ 2 3 => 3 2

朴灿烈づ我的快乐病毒、/ 2022年06月01日 00:54/ 0 赞/ 151 阅读

相关平衡二叉树

平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和 E.M.

墨蓝/ 2022年05月28日 08:57/ 0 赞/ 394 阅读

相关平衡二叉树

平衡二叉树又称AVL树。它或者是颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定

骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 238 阅读

相关平衡二叉树【leetcode - 110 - 简单】

胡扯：这个题做的时间还是比较长的，虽然只是一个简单题。不过在做的过程中一直觉得自己可以做出来的。哈哈，最后代码不是很好，只打败百分之36的人，这也是想到的，毕竟写

刺骨的言语ヽ痛彻心扉/ 2022年03月30日 14:22/ 0 赞/ 160 阅读

相关平衡二叉树

平衡二叉树介绍是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出，因此一般也称作AVL树，AVL树本质还是一棵二叉查找树，只是在其基础

青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 322 阅读

相关平衡二叉树 (平衡查找树)

平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上

小咪咪/ 2021年10月29日 07:24/ 0 赞/ 438 阅读

相关二叉平衡树

二叉平衡树说起这个树，我找了整整两天的时间，刚开始考虑的不周全，然后就一直该一直该，一直加一直加。定义：它是一颗空疏或它的左右两个子树的高度差的绝对值不超过

Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 439 阅读