1382.将二叉搜索树变平衡

链接：1382.将二叉搜索树变平衡
难度：Medium
标签：贪心、树、深度优先搜索、二叉搜索树、分治、二叉树
简介：给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

题解 1 - typescript

• 编辑时间：2021-08-07
• 执行用时：148ms
• 内存消耗：53.2MB
• 编程语言：typescript
• 解法介绍：中序遍历排序后依次插入。

function balanceBST(root: TreeNode | null): TreeNode | null {
  const q: TreeNode[] = [];
  inorder(root);
  return build(q);
  function inorder(node: TreeNode | null) {
    if (node === null) return;
    const { left, right } = node;
    inorder(left);
    q.push(node);
    inorder(right);
  }
  function build(list: TreeNode[]): TreeNode | null {
    if (list.length === 0) return null;
    const mid = (0 + list.length - 1) >> 1;
    const node = list[mid];
    node.left = build(list.slice(0, mid));
    node.right = build(list.slice(mid + 1));
    return node;
  }
}