共计 1887 个字符，预计需要花费 5 分钟才能阅读完成。
110. 均衡二叉树
题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/balanced-binary-tree
题目
给定一个二叉树，判断它是否是高度均衡的二叉树。
本题中，一棵高度均衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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。
也就是说，只有所有子树都是均衡二叉树的条件下，整个二叉树才是均衡二叉树。那么咱们用递归的思维来解决这个问题。
递归（自顶向下）
在这里，咱们先用自顶向下的思路来去解决这个问题。
下面说了，要判断一个二叉树是否是均衡二叉树？要看所有子树是否都是均衡二叉树，那么这里须要比拟每个节点左右子树的高度差绝对值，不能超过 1。
那么，首先思考计算节点的高度 height，会有以下状况：
- 若以后节点为空节点，那么返回高度 0；
- 若以后节点为非空节点，那么这里返回左右子树中的最大高度 + 1。
而后，要思考的是如何去判断是否均衡？状况如下：
- 先解决非凡状况，如果根节点为空，间接返回 True；
-
根节点非空，那么这里用先序遍历递归，对上面三种状况进行判断：
- 判断以后子树是否是均衡二叉树；
- 判断以后子树的左子树是否是均衡二叉树；
- 判断以后子树的右子树是否是均衡二叉树。
具体的代码见【代码实现 # 递归（自顶向下）】
递归（自底向上）
在下面 递归（自顶向下） 的办法中，会产生大量反复计算，工夫复杂度较高。
这里具体的做法如下：
-
设定终止条件：
- 越过叶子节点时，返回高度 0；
- 若左右子树任一高度为 -1 的状况下，代表左右子树不均衡，间接返回 -1。（这里左右子树高度由上面的左右子树高度差绝对值是否超过 1 决定）
- 如果以后节点左右子树的高度差的绝对值不超过 1 时，那么返回左右子树最大高度 +1；
- 如果以后节点左右子树的高度差的绝对值超过 1 时，返回 -1，示意子树不均衡。
具体的代码见【代码实现 # 递归（自底向上）】
代码实现
# 递归（自顶向下）# 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:
def depth(root):
""" 求以后节点的深度
Args:
root: 节点
Returns:
返回节点深度
"""
# 节点为空，返回高度 0
if not root:
return 0
# 否则返回左右子树最大高度值 +1
return max(depth(root.left), depth(root.right)) + 1
# 根节点为空，间接返回 True
if not root:
return True
# 否则递归判断
# 1. 以后子树是否均衡
# 2. 以后子树左子树是否均衡
# 3. 以后子树右子树是否均衡
return abs(depth(root.left)-depth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
# 递归（自底向上）# 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:
def helper(root):
if not root:
return 0
left = helper(root.left)
# 当左右子树高度为 -1，示意不均衡返回 -1
if left == -1:
return -1
right = helper(root.right)
if right == -1:
return -1
# 判断左右子树高度差的绝对值是否不超过 1
return -1 if abs(left-right) > 1 else max(left, right) + 1
return helper(root) >= 0实现后果
欢送关注
公众号【书所集录】
正文完
