一天一大 lee(平衡二叉树)难度:简单-Day20200817

    3
   / \
  9  20
    /  \
   15   7

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  if (!root) return true
  return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);

  // 计算传入节点的高度 => 左子节点+右子节点高度
  function height(node) {
    if (!node) return 0
    return Math.max(height(node.left), height(node.right))+1
  }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function (root) {
  return height(root) >= 0;

  function height(node) {
    if (!node) return 0
    let left = height(node.left),
        right = height(node.right);
    // 存在左右节点高度差值大于1的节点，则整个二叉树都不可能是平衡二叉树
    if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
      return -1;
    } else {
      // 如果节点平衡返回节点高度
      return Math.max(left, right) + 1;
    }
  }
}