LeetCode | 面试题 04.04. 检查平衡性【Python】

野性酷女 2022-11-08 14:11 84阅读 0赞

## 问题 ##

[力扣][Link 1]

实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

**示例 1:**

给定二叉树 [3,9,20,null,null,15,7]
        3
       / \
      9  20
        /  \
       15   7
    返回 true 。

**示例 2:**

给定二叉树 [1,2,2,3,3,null,null,4,4]
          1
         / \
        2   2
       / \
      3   3
     / \
    4   4
    返回 false 。

## 思路 ##

**递归**

不止根节点左右高度差小于等于1，左右子树也要满足平衡

## 代码 ##

### Python3 ###

# 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
            
            # 计算树的高度
            def height(root):
                if not root:
                    return 0
                return max(height(root.left), height(root.right)) + 1
            
            # 不止根节点左右高度差小于等于1，左右子树也要满足平衡
            return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

## 链接 ##

[GitHub][]

[Link 1]: https://leetcode-cn.com/problems/check-balance-lcci/
[GitHub]: https://github.com/Wonz5130/LeetCode-Solutions/tree/master/solutions/Interview-04.04-Check-Balance-LCCI

发表评论取消回复

表情：

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

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

相关阅读

相关抖音X_Gorgon 0404

coding:utf-8 from time import time from hashlib import md5 from co

朴灿烈づ我的快乐病毒、/ 2023年09月26日 16:09/ 0 赞/ 15 阅读

相关 LeetCode | 面试题 01.07. 旋转矩阵【Python】

> LeetCode 面试题 01.07. 旋转矩阵【Medium】【Python】【数学】问题 [力扣][Link 1] 给你一幅由 N × N 矩阵表示的图像，

浅浅的花香味﹌/ 2023年07月24日 14:59/ 0 赞/ 58 阅读

相关 LeetCode | 面试题 01.06. 字符串压缩【Python】

> LeetCode 面试题 01.06. 字符串压缩【Easy】【Python】【双指针】问题 [力扣][Link 1] 字符串压缩。利用字符重复出现的次数，编写

Dear 丶/ 2023年07月15日 12:48/ 0 赞/ 36 阅读

相关 LeetCode | 面试题 04.10. 检查子树【Python】

> LeetCode 面试题 04.10. 检查子树【Medium】【Python】【DFS】问题 [力扣][Link 1] 检查子树。你有两棵非常大的二叉树：T1

╰+攻爆jí腚メ/ 2023年07月10日 08:28/ 0 赞/ 30 阅读

相关程序员面试金典-面试题04.04-检查二叉树平衡性

程序员面试金典-面试题04.04-检查二叉树平衡性实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。

待我称王封你为后i/ 2023年01月10日 12:00/ 0 赞/ 156 阅读

相关 leetcode算法题--检查两个数组是否相等（python实现）

题目：给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同，返回 true ；否则，返回 false 。题目示范：输入：wor

待我称王封你为后i/ 2022年12月23日 12:27/ 0 赞/ 206 阅读

相关 LeetCode | 面试题 17.12. BiNode【Python】

问题 [力扣][Link 1] 二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链

落日映苍穹つ/ 2022年11月12日 10:59/ 0 赞/ 211 阅读

相关 LeetCode | 面试题 04.12. 求和路径【Python】

问题 [力扣][Link 1] 给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径

た入场券/ 2022年11月10日 00:46/ 0 赞/ 180 阅读

相关 LeetCode | 面试题 04.04. 检查平衡性【Python】

问题 [力扣][Link 1] 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。示例 1:

野性酷女/ 2022年11月08日 14:11/ 0 赞/ 85 阅读

相关 leetcode 面试题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我就是我/ 2022年09月02日 11:54/ 0 赞/ 257 阅读