110. 平衡二叉树

[swiftwind0405]

方法一：暴力法

解题思想：
自顶向下的比较每个节点的左右子树的最大高度差，如果二叉树中每个节点的左右子树最大高度差小于等于 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 -1
    return 1 + Math.max(depth(node.left), depth(node.right))
}

复杂度分析：

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