Balanced Binary Tree
数组 root 表示一棵二叉树。根节点位于索引 0，索引 i 的子节点位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置，末尾可能会有多余的 -1 项。
如果这棵树是高度平衡的，则返回 true，否则返回 false。高度平衡是指每个节点的左子树和右子树的高度之差最多为 1。子树的高度是其最长向下路径上的节点数；空子树的高度为 0。
函数
- rootinteger-array
- 二叉树的层序遍历，空位用 -1 表示
- 返回值boolean
- 如果每个节点的两个子树高度之差都不超过 1，则为 true，否则为 false
约束条件
1 ≤ root.length ≤ 32767- 每个
root[i]都是-1，或是满足0 ≤ root[i] ≤ 105的值。 root[0]永远不会是-1，因此树至少有一个节点。- 数组末尾可能会在最后一个节点之后包含额外的
-1项。 - 空位置的两个子节点也都是空的，并且深度最多为
14。 - 节点的值各不相同。
示例
- 输入
- root = [5, 2, 9, -1, -1, 7, 11]
- 输出
- true
- 解释
- 根节点的左子树只有一个节点
2，高度为1。它的右子树由9、7、11组成，高度为2。它们的高度相差1，其他每个节点的两棵子树高度都相等。
- 输入
- root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
- 输出
- false
- 解释
- 根节点的两侧高度都是
3，但节点3不满足条件：它的左子树1、0的高度为2，而右子树为空。
- 输入
- root = [4, 2, -1, 1]
- 输出
- false
- 解释
- 根节点的左侧有一条链，节点值为
2、1，高度为2；右侧没有节点，高度为0。两侧高度相差2，差距太大了。
进阶
你能使用显式栈，在不使用递归的情况下检查这棵树吗？
提示
逐个打开提示，每个都会多透露一点。
一棵树可能在根节点通过测试，却在下一层失败。要在某个节点检查它，你需要哪两个数字？
你需要知道节点两个子树的高度。如果在每个节点都从头计算高度，就会多次遍历相同的节点。能不能在访问一个节点时，同时把它的高度以及它下面的所有节点是否都通过的信息传给父节点？
编写一个后序函数，返回子树的高度；如果子树不平衡，则返回
-1。在某个节点处，如果某个子节点返回了-1，或者左右子树的高度相差超过1，则返回-1；否则返回1 + max(left, right)。
题解
这条规则适用于每个节点，因此即使根节点看起来平衡，树的下层仍可能不满足规则，就像第二个示例在 3 处那样。后序遍历会为每个子树计算一次高度，并在发现不满足规则时立即向上传递，在 O(n) 时间内完成。
重新计算每个节点的高度
思路
把定义转换成代码。空位置的 height(i) 为 0，其他位置的值比两个子节点中较高的那个多 1。比较每个实际节点的两个子节点的高度，第一个高度差超过 1 的节点会让答案变成 false。
每次检查都会遍历该节点下方的整棵子树，因此每个节点都会在它上方的每个节点进行检查时被遍历一次：O(n·h)。最多有 14 层时，一棵有 16,383 个节点的满树需要约 2 × 10^5 步。一条有 n 个节点的链需要 O(n²)。
算法
- 将越过末尾的索引或值为
-1的索引对应的height(i)定义为0；对于真实节点，将其定义为1 + max(height(2*i+1), height(2*i+2))。 - 访问每个存有真实节点的索引
i。 - 如果
height(2*i+1)和height(2*i+2)的差大于1，则返回false。 - 如果循环结束时没有发现失败，则返回
true。
def isBalanced(root):
n = len(root)
def height(i):
# The number of nodes on the longest downward path from index i.
if i >= n or root[i] == -1:
return 0
return 1 + max(height(2 * i + 1), height(2 * i + 2))
# Check every real node, measuring both subtrees from scratch.
for i in range(n):
if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
return False
return True一次后序遍历，报告高度或失败
思路
检查一个节点时，需要知道它的两个子树的高度，而该节点也需要用这两个高度来报告自身的高度。因此，只需进行一次后序遍历就能同时获取它们：每次调用都会在两个子节点都返回后，返回该节点子树的高度。
较低位置的失败也必须向上传递。实际高度永远不会是负数，因此用 -1 表示失败：如果某个子节点返回了 -1，或者两个子树的高度相差超过 1，这次调用就返回 -1。在第二个示例中，3 看到的高度是 2 和 0，于是返回 -1，根节点会直接传递这个结果，不再访问右侧。
每个节点只会进入一次，因此时间复杂度为 O(n)，调用栈上的调用数为 O(h)。
算法
- 编写
check(i)。如果索引超出末尾，或索引为-1，则返回0。 - 计算
left = check(2*i+1)。如果它是-1，则返回-1。 - 计算
right = check(2*i+2)。如果它是-1，或者left和right的差大于1，则返回-1。 - 否则，返回
1 + max(left, right)。 - 返回
check(0)是否不等于-1。
def isBalanced(root):
n = len(root)
def check(i):
# The height of the subtree at index i, or -1 if it is not balanced.
if i >= n or root[i] == -1:
return 0
left = check(2 * i + 1)
if left == -1:
return -1
right = check(2 * i + 2)
if right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(0) != -1
易错点和边界情况
- 只检查根节点。在第二个示例中，根节点两侧的高度都是
3，但节点3的高度差为2。 - 比较最浅和最深的叶节点。高度为
6的最小平衡树，其叶节点深度为4和6，其中每个节点都符合要求。 - 向上返回时丢失失败标记。如果子节点返回
-1，而父节点计算1 + max(-1, 2)，失败标记就会变回高度。 - 把数组长度当作树的高度。末尾的
-1项会让数组长度超过树的深度。 - 在 Lua 和 R 中，数组从 1 开始索引。对于
2*i+1，节点索引保持从 0 开始，并读取root[i + 1]。
常见问题3
平衡二叉树的时间复杂度是多少？
一次后序遍历会访问每个节点一次：对于高度为 h 的树，时间复杂度为 O(n)，栈空间复杂度为 O(h)。在每个节点重新计算高度需要 O(n·h)，在链状树上会变成 O(n²)。
二叉树的高度平衡是什么意思？
在每个节点，左子树和右子树的高度差最多为 1。AVL 树会在每次插入和删除后恢复这一属性，因此树高始终为 O(log n)。
完全二叉树总是平衡的吗？
是的。完全二叉树的每一层都是满的，只有最后一层可能例外，并且最后一层从左向右填充，因此任意节点的两个子树高度之差最多为 1。反过来则不成立：平衡二叉树的最后一层左侧可能存在空缺。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isBalanced(root):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [5, 2, 9, -1, -1, 7, 11]
预期输出
true