力扣刷题笔记：110.平衡二叉树（深度优先搜索dfs，必能看懂）

朱雀 2022-11-07 11:42 129阅读 0赞

## 题目： ##

110、平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：

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

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]

> 输入：root = \[3,9,20,null,null,15,7\]  
> 输出：true

示例 2：

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

> 输入：root = \[1,2,2,3,3,null,null,4,4\]  
> 输出：false

示例 3：

> 输入：root = \[\]  
> 输出：true

提示：

> 树中的节点数在范围 \[0, 5000\] 内  
> \-10^4 <= Node.val <= 10^4

## 题解思路： ##

由于平衡二叉树定义为就是\*\*一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。\*\*用伪代码描述就是：

if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是平衡二叉树 and root.right 也是平衡二叉树:
        print('是平衡二叉树')
    else:
        print('不是平衡二叉树')

而 root.left 和 root.right 如何判断是否是二叉平衡树就和 root 是一样的了，可以看出这个问题有明显的递归性。

因此我们首先需要知道如何计算一个子树的高度。这个可以通过递归的方式轻松地计算出来。计算子树高度的 Python 代码如下：

def dfs(node, depth):
        if not node: return 0
        l = dfs(node.left, depth + 1)
        r = dfs(node.right, depth + 1)
        return max(l, r) + 1

**复杂度分析**

时间复杂度：对于 isBalanced 来说，由于每个节点最多被访问一次，这部分的时间复杂度为 O(N)，而 dfs 函数 每次被调用的次数不超过 log N，因此总的时间复杂度为 O(NlogN)，其中 N 为 树的节点总数。

空间复杂度：由于使用了递归，这里的空间复杂度的瓶颈在栈空间，因此空间复杂度为 O(h)，其中 h 为树的高度。

## 题解python代码： ##

class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            def dfs(node, depth):
                if not node: return 0
                l = dfs(node.left, depth + 1)
                r = dfs(node.right, depth + 1)
                return max(l, r)  + 1
    
            if not root: return True
            if abs(dfs(root.left, 0)-dfs(root.right, 0))>1: return False
    
            return self.isBalanced(root.left) and self.isBalanced(root.right)

> 作者：fe-lucifer  
> 链接：[https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-zhuan-ti-by-fe-lucifer/][https_leetcode-cn.com_problems_balanced-binary-tree_solution_ping-heng-er-cha-shu-zhuan-ti-by-fe-lucifer]  
> 来源：力扣（LeetCode）[https://leetcode-cn.com/problems/balanced-binary-tree/][https_leetcode-cn.com_problems_balanced-binary-tree]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]: /images/20221023/a8a5beb163c048018bbed2f09b4b6828.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70 1]: /images/20221023/56d739905b194a67aa2045aee08e35d0.png
[https_leetcode-cn.com_problems_balanced-binary-tree_solution_ping-heng-er-cha-shu-zhuan-ti-by-fe-lucifer]: https://leetcode-cn.com/problems/balanced-binary-tree/solution/ping-heng-er-cha-shu-zhuan-ti-by-fe-lucifer/
[https_leetcode-cn.com_problems_balanced-binary-tree]: https://leetcode-cn.com/problems/balanced-binary-tree/