什么是平衡二叉树

平衡二叉树简称 AVL 树。平衡二叉树指的是任意结点的左右子树高度差绝对值都不大于1的二叉搜索树。下面这个例子就是一个平衡二叉树：

    4
   /  \
  2    5
 / \
1   3

为什么有平衡二叉树

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

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

普通的二叉搜索树查找操作的时间复杂度最坏情况下为 O(N) 。由于平衡二叉树利用了二分思想，使得查找操作的时间复杂度降为 O(logN)。

平衡二叉树的判定

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

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

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

返回 false 。

const root = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 3,
            left: {
                val: 4
            },
            right: {
                val: 4
            }
        },
        right: {
            val: 3
        }
    },
    right: {
        val: 2
    }
};

function isBalanced(root) {
    let flag = true;

    function dfs(root) {
        if (!flag || !root) 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;
}

平衡二叉树的构造

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

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是平衡的。
如果有多种构造方法，请你返回任意一种。

function balanceBST(root) {
  const nums = [];

  function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
  }

  function inorder(root) {
    if (!root) return root;
    inorder(root.left);
    nums.push(root.val);
    inorder(root.right);
  }

  function buildAVL(low, high) {
    if (low > high) return null;

    const mid = Math.floor((low + high) / 2);
    const cur = new TreeNode(nums[mid]);
    cur.left = buildAVL(low, mid - 1);
    cur.right = buildAVL(mid + 1, high);
    return cur;
  }

  inorder(root);
  return buildAVL(0, nums.length - 1);
}