判断是否是平衡二叉树

1. 题目描述

判断一棵树是不是平衡二叉树。

2. 思路分析

思路一：计算出左右子树的深度，然后检查差。递归继续判断左子树和右子树是不是平衡二叉树。

思路二：先计算左子树和右子树是不是平衡二叉树，然后再计算本身是不是平衡二叉树。

关于思路二为什么能比思路一更好，请看代码。

3. 代码实现

3.1 树的深度

先递归实现树的深度函数：

class Node {
  /**
   *
   * @param {Number} value
   * @param {Node} left
   * @param {Node} right
   */
  constructor(value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

/**
 * 获取二叉树的深度
 *
 * @param {Node} root
 */
function treeDepth(root) {
  if (!root) {
    return 0;
  }

  const leftDepth = treeDepth(root.left);
  const rightDepth = treeDepth(root.right);
  return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

3.2 思路一

这种思路慢是因为：节点被重复计算了。得出 leftDepth 计算了一遍 root.left ，最后还要再调用自身计算 root.left。尤其是叶子节点，会造成很多的计算浪费。

/**
 * 判断是否是平衡二叉树
 *
 * @param {Node} root
 */
function isBalanced(root) {
  if (!root) {
    return true;
  }

  const leftDepth = treeDepth(root.left);
  const rightDepth = treeDepth(root.right);
  const diff = Math.abs(leftDepth - rightDepth);
  if (diff > 1) {
    return false;
  }

  return isBalanced(root.left) && isBalanced(root.right);
}

3.3 思路二

先遍历和计算左右子树，最后计算本身。不需要重复计算。

/**
 * 优化：判断是否是平衡二叉树
 *
 * @param {Node} root
 * @param {Object} obj
 */
function isBalanced2(root, obj = {}) {
  if (!root) {
    obj.depth = 0;
    return true;
  }

  const left = {},
    right = {};
  if (isBalanced2(root.left, left) && isBalanced2(root.right, right)) {
    const diff = Math.abs(left.depth - right.depth);
    if (diff > 1) {
      return false;
    }

    obj.depth = 1 + (left.depth > right.depth ? left.depth : right.depth);
    return true;
  } else {
    return false;
  }
}

3.4 测试

/**
 * 测试代码
 */
const root = new Node(
  1,
  new Node(2, new Node(4), new Node(5, new Node(7))),
  new Node(3, null, new Node(6))
);

// 测试树的深度
console.log(treeDepth(root)); // output: 4

// 判断是否是平衡二叉树
console.time();
console.log(isBalanced(root)); // true
console.timeEnd(); // 0.594ms

// 优化算法：判断是否是平衡二叉树
console.time();
console.log(isBalanced2(root)); // true
console.timeEnd(); // 0.242ms