特殊的二叉树-平衡二叉树

二叉搜索树是二叉树的特例，平衡二叉树则是二叉搜索树的特例。

什么是平衡二叉树

任意结点的左右子树高度差绝对值都不大于1的二叉搜索树。

为什么要有平衡二叉树

平衡二叉树的出现，是为了降低二叉搜索树的查找时间复杂度

二叉搜索树的妙处就在于它把“二分”这种思想以数据结构的形式表达了出来。

平衡二叉树的判定

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。

    3
   / \
  9  20
    /  \
   15   7

结果：true

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

结果：false

function isBalanced(root) {
  let flag = true;
  function dfs(root) {
    // 如果是空树，高度记为0；如果flag已经false了，那么就没必要往下走了，直接return
    if (!root || !flag) return 0;
    const left = dfs(root.left);
    const right = dfs(root.right);
    if (Math.abs(left - right) > 1) {
      flag = false
      // 后面再发生什么已经不重要了，返回一个不影响回溯计算的值
      return 0
    }
    // 返回当前子树的高度
    return Math.max(left, right) + 1
  }
  dfs(root)
  return flag
}

平衡二叉树的构造

给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

别忘了，二叉搜索树的中序遍历序列是有序的！所谓有序数组，完全可以理解为二叉搜索树的中序遍历序列啊，对不对？现在树都给到咱们手里了，求它的中序遍历序列是不是非常 easy？如果能把中序遍历序列求出来，这道题是不是就跟之前做过那道是一模一样的解法了？

没错，这道题的解题思路正是：

1. 中序遍历求出有序数组
2. 逐个将二分出来的数组子序列“提”起来变成二叉搜索树

function balanceBST(root) {
  // 中序遍历得到有序数组
  const result = [];
  function inOrderTrans(root) {
    if (root) {
      if (root.left) inOrderTrans(root.left);
      result.push(root.val);
      if (root.right) inOrderTrans(root.right)
    }
  }
  inOrderTrans(root);

  function buildAVL(low, high) {
    // 若 low > high，则越界，说明当前索引范围对应的子树已经构建完毕
    if (low > high) {
      return null
    }
    const mid = Math.floor((low + high) / 2);
    const node = new TreeNode(result[mid]);
    node.left = buildAVL(low, mid - 1);
    node.right = buildAVL(mid + 1, high);
    return node;
  }

  return buildAVL(0, result.length - 1)
}