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
}