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

野性酷女 2022-11-08 14:11 33阅读 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 条评论，33人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关 LeetCode | 面试题 04.06. 后继者【Python】

问题 [力扣][Link 1] 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。如果指定节点没有对应的“下一个”节点，则返回null。示

分手后的思念是犯贱/ 2022年11月09日 01:27/ 0 赞/ 97 阅读

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

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

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

相关 python面试题

过完春节，一共参加了 5 个公司的面试。第一家公司，通过了 2 轮技术面试，但是薪资不够理想。第二个公司，被面试的测试专家虐的不要不要的，挂了，但也知道了自己很多不足之处。后面

阳光穿透心脏的1/2处/ 2022年10月03日 00:46/ 0 赞/ 234 阅读

相关 leetcode 面试题

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

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

相关 python 面试题

Python面试题以及答案 1.用Python求出斐波那契数列第10位 def fib(n): a, b = 1, 1 for

不念不忘少年蓝@/ 2022年08月28日 12:39/ 0 赞/ 208 阅读

相关 python面试题

1. 企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高　　　于10万元，低于20万元时，低于10万元的部分按10%提成，高于1

Myth丶恋晨/ 2022年06月02日 01:37/ 0 赞/ 238 阅读