【LeetCode 1382】将二叉搜索树变平衡

今天药忘吃喽~ 2023-02-23 08:12 5阅读 0赞

#### 题目描述 ####

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

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

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

示例：

![在这里插入图片描述][20200706105602902.png]  
![在这里插入图片描述][20200706105620830.png]

输入：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 到 104 之间。
 *  树节点的值互不相同，且在 1 到 105 之间。

#### 解题思路 ####

之前做过一个题就是将一个有序数组转化为高度平衡的二叉搜索树：[【LeetCode 108】将有序数组转换为二叉搜索树][LeetCode 108]，可以根据那个题思路来解答。

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

#### 代码实现 ####

/** * 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)
    };

#### 提交结果 ####

![在这里插入图片描述][20200706105515817.png]

[20200706105602902.png]: https://img-blog.csdnimg.cn/20200706105602902.png?
[20200706105620830.png]: https://img-blog.csdnimg.cn/20200706105620830.png
[LeetCode 108]: https://blog.csdn.net/qq_42033567/article/details/106980794
[20200706105515817.png]: https://img-blog.csdnimg.cn/20200706105515817.png