平衡二叉树 - wangshengliang

例如这么一个序列：

;[3, 5, 1, 6, 7, 2, 9, 8]

最终构建出来的二叉树为：

在使用二叉搜索树进行搜索的时候，搜索的次数取决二叉搜索树的层数。层数越少，那么搜索的次数自然就越少。

🙋什么是平衡二叉树？

在树的任何一个结点处，其左子树和右子树的高度差（有时也称为“深度差”）不会超过一定的限制（通常是 1）。这种限制保证了树的整体“平衡性”，从而使得在最坏情况下进行搜索、插入、删除等操作时，都能保持接近O(log⁡n) 的时间复杂度。

下面是一些非平衡二叉树的示例：

A
 \
  B
   \
    C
     \
      D

    A
   /
  B
 / \
C   D
   /
  E
 /
F

    A
   / \
  B   C
 / \
D   E
   /
  F
 /
G

下面就是一个平衡的二叉树

    A
   / \
  B   C
 / \
D   E

📚任务，就是书写一个方法，来判断一颗树是否是平衡二叉树。

/**
 * 计算以 node 节点为根的子树的高度
 * 在计算的过程中会判断子树是否平衡
 * 如果子树不平衡，返回 - 1
 * 如果子树平衡，返回该子树的高度
 */
function checkHeight(node) {
  // 如果节点为空，子树高度为 0
  if (node === null) return 0

  // 接下来需要递归的去计算左子树和右子树的高度
  const leftHeight = checkHeight(node.left)
  // 如果左子树不平衡，直接返回 -1
  if (leftHeight === -1) return -1

  const rightHeight = checkHeight(node.right)
  // 如果右子树不平衡，直接返回 -1
  if (rightHeight === -1) return -1

  // 现在得到了左右子树各自的高度
  // 接下来计算左右子树高度差
  // 如果左右子树的高度差大于 1，说明当前的树不平衡，返回 -1
  if (Math.abs(leftHeight - rightHeight) > 1) return -1

  // 返回以当前 node 节点为根节点，子树的高度
  // 这里看 node 节点的左右子树谁更大就取谁的值
  return Math.max(leftHeight, rightHeight) + 1
}

function isBalanced(root) {
  return checkHeight(root) !== -1
}

序列为 [4, 2, 7, 1, 3, 6, 5]，形成的二叉搜索树为：

序列为[10, 5, 15, 3, 7, 12, 20, 6, 8] ，形成的二叉搜索树为：

    10
   /  \
  5    15
 / \   / \
3   7 12  20
   / \
  6   8

-EOF-