LeetCode 110. 平衡二叉树 | Python

审题，题目要求给定的二叉树是否是高度平衡二叉树。关于高度平衡二叉树，题目给的定义是：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 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