### 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

3   / \  9  20    /  \   15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

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

Return false.

### Analyze

• 自顶向下
• 终止条件: 当前访问节点为 null;
• 循环逻辑: 当前节点的左、右子节点都为 height-balanced;
/** * 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 isBalanced(root.left) && isBalanced(root.right) && Math.abs(deep(root.left) - deep(root.right)) <= 1};
// the thought is same as [104.Maximum Depth of Binary Tree](https://github.com/MuYunyun/blog/blob/master/LeetCode/104.Maximum_Depth_of_Binary_Tree.md)var deep = (node) => {  if (!node) return 0  return Math.max(deep(node.left), deep(node.right)) + 1}
• 自底向上
• 策略: 提前终止
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) {  return deep(root) === -1 ? false : true};
var deep = (node) => {  if (!node) return 0  const leftNode = deep(node.left)  if (leftNode === -1) return -1  const rightNode = deep(node.right)  if (rightNode === -1) return -1  return Math.abs(leftNode - rightNode) <= 1 ? Math.max(leftNode, rightNode) + 1 : -1}