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

男娘i 2022-06-01 04:49 217阅读 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 条评论，217人围观）

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

相关阅读

相关 LeetCode_二叉平衡树_简单_110.平衡二叉树

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义

缺乏、安全感/ 2023年10月07日 20:24/ 0 赞/ 29 阅读

相关树（二）平衡二叉树

[树（一）二叉查找树][Link 1] [树（三）红黑树与平衡二叉树的区别][Link 2] 1 为什么有平衡二叉树二叉查找树（二叉搜索树）

迷南。/ 2023年06月22日 04:22/ 0 赞/ 19 阅读

相关树：平衡二叉树

1，二叉排序树问题对于一个有序数组`{1, 2, 3, 4, 5}`，其生成的二叉排序树如下；由图可见，最终形成一个类似单链表形式的二叉树，对插入速度没有影响，但

╰+哭是因爲堅強的太久メ/ 2023年02月28日 01:25/ 0 赞/ 21 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关平衡二叉树

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

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

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

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

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