1382. 将二叉搜索树变平衡

1. 题目描述

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

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

如果有多种构造方法，请你返回任意一种。

示例：

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

提示：

• 树节点的数目在 1 到 10 之间。
• 树节点的值互不相同，且在 1 到 10 之间。

  2. 解题思路

  这个题目和108题的思路类似。

我们知道二叉搜索树的中序遍历是一个有序数组，那么我们就可以将题目给出的二叉搜索树进行中序遍历，将遍历得到的有序数组转化为平衡的二叉搜索树。其中后半部分和之前的解题思路完全一致。

3. 代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var balanceBST = function(root) {
   // 初始化一个数组用来储存中序遍历的结果
   const nums = []
   // 对二叉搜索树进行中序遍历
   function inorder(root){
       if(!root){
           return 
       }
       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-low)/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)
};

4. 提交结果