31 - 平衡二叉树

题目

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

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
  /   \

​ 9 20 / 15 7 返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

           1
 /   \
2      2

/ 3 3 / 4 4 返回 false 。

解答

var isBalanced = function (root) {
  return depth(root) !== -1;
};

const depth = function (root) {
  if (!root) {
    return 0
  }
  let left = depth(root.left);
  if (left === -1) {
    return -1
  }
  let right = depth(root.right);
  if (right === -1) {
    return -1
  }
  return Math.abs(left - right) < 2 ? Math.max(left, right) + 1: -1
}

Runtime: 60 ms, faster than 96.59% of JavaScript online submissions for Balanced Binary Tree.

Memory Usage: 37.4 MB, less than 79.49% of JavaScript online submissions for Balanced Binary Tree.

作者：powcai

链接：https://leetcode-cn.com/problems/two-sum/solution/zi-ding-xiang-xia-he-zi-di-xiang-shang-by-powcai/

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

执行用时 :104 ms, 在所有 JavaScript 提交中击败了74.49%的用户

内存消耗 :37.7 MB, 在所有 JavaScript 提交中击败了29.70%的用户