2. 平衡二叉树

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度（深度）差的绝对值不超过 1 。

判定条件就是左右子树：那么一定是后序遍历

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

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

输入：root = [] 输出：true

下两种方法均基于以下性质推出： 此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1

解答一：自顶向下的前需遍历（暴力法）

解题思路： 自顶向下的比较每个节点的左右子树的最大高度差，如果二叉树中每个节点的左右子树最大高度差小于等于 1 ，即每个子树都平衡时，此时二叉树才是平衡二叉树

var isBalanced = function (root) {
  if (!root) return true;
  return Math.abs(depth(root.left) - depth(root.right)) <= 1
    && isBalanced(root.left)
    && isBalanced(root.right)
}
var depth = function (node) {
  if (!node) return 0;
  return 1 + Math.max(depth(node.left), depth(node.right))
}

复杂度分析：

时间复杂度：O (nlogn)，计算 depth 存在大量冗余操作
空间复杂度：O (n)

解答二：自底向上（剪枝优化）

解题思路： 利用后续遍历二叉树（左右根），从底至顶返回子树最大高度，判定每个子树是不是平衡树 ，如果平衡，则使用它们的高度判断父节点是否平衡，并计算父节点的高度，如果不平衡，返回 -1 。

遍历比较二叉树每个节点 的左右子树深度：

1. 比较左右子树的深度，若差值大于 1 则返回一个标记 -1 ，表示当前子树不平衡
2. 左右子树有一个不是平衡的，或左右子树差值大于 1 ，则二叉树不平衡
3. 若左右子树平衡，返回当前树的深度（左右子树的深度最大值 +1 ）

二叉树前序遍历

const balanced = function balanced(node) {
  if (!node) return 0;
  const left = balanced(node.left);
  const right = balanced(node.right);
  // 先查看左右子树的情况，再根据此做出判断
  // 不平衡条件：左右不平衡 / 左右子树高度差值大于1
  if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
    return -1;
  }
  return 1 + Math.max(left, right);
}
const isBalanced = function isBalanced(root) {
  return balanced(root) !== -1;
};

复杂度分析：
时间复杂度：O (n)
空间复杂度：O (n)