一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
1、110. 平衡二叉树 方法一： 从顶到底，depth递归计算一个节点的最大高度， 然后判断一个节点和左子树以及右子树是平衡节点（递归）， 此处会有大量重复的高度计算。 时间复杂度O(n2)
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root: return True
leftDepth = self.depth(root.left)
rightDepth = self.depth(root.right)
return abs(leftDepth - rightDepth) bool:
if not node:
return 0
leftDepth = self.depth(node.left)
rightDepth = self.depth(node.right)
return max(leftDepth, rightDepth) + 1
方法二：从底至顶（提前阻断法）
- 对二叉树做深度优先遍历DFS，递归过程中：
- 终止条件：当DFS越过叶子节点时，返回高度0；
- 返回值：
- 从底至顶，返回以每个节点root为根节点的子树最大高度(左右子树中最大的高度值加1max(left,right) + 1)；
- 当我们发现有一例 左/右子树高度差 ＞ 1 的情况时，代表此树不是平衡树，返回-1；
- 当发现不是平衡树时，后面的高度计算都没有意义了，因此一路返回-1，避免后续多余计算。
- 最差情况是对树做一遍完整DFS，时间复杂度为 O(N)。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
return self.depth(root) != -1
# 从底至顶（提前阻断法）, DFS
def depth(self, node: TreeNode) -> bool:
if not node: return 0
leftDepth = self.depth(node.left)
# 左子树不平衡
if leftDepth == -1: return -1
rightDepth = self.depth(node.right)
# 左子树不平衡
if rightDepth == -1: return -1
return max(leftDepth, rightDepth) + 1 if abs(leftDepth - rightDepth) TreeNode:
if len(nums) == 0:
return None
start = 0
end = len(nums) - 1
return self.buildTree(nums, 0, end)
# 二分法构建平衡树
def buildTree(self, nums: List[int], start: int, end: int) -> TreeNode:
if start > end:
return None
mid = (start + end) >> 1
# 中值作为根节点
root = TreeNode(nums[mid])
## 两边数据，分别构建左、右子树
root.left = self.buildTree(nums, start, mid - 1)
root.right = self.buildTree(nums, mid + 1, end)
return root
方法二：
