leetcode5179. 将二叉搜索树变平衡

leetcode5179. 将二叉搜索树变平衡

三月 22, 2020

5179. 将二叉搜索树变平衡

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

如果一颗二叉搜索树中，任何节点两棵子树的高度差不超过 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        traverse(root);
        TreeNode newRoot=build(0,list.size()-1);
        return newRoot;
        
    }
    public TreeNode build(int start,int end){
        if(start>end)return null;
        int mid=(start+end)>>1;
        TreeNode newRoot=list.get(mid);
        newRoot.left=build(start,mid-1);
        newRoot.right=build(mid+1,end);
        return newRoot;
    }
    public LinkedList<TreeNode>list=new LinkedList<>();
    public void traverse(TreeNode root){
        if(root==null)return ;
        traverse(root.left);
        list.add(root);
        traverse(root.right);
    }
}

周赛终于能够做出来三道题了，可能是因为这次简单。这次第四道题是一点思路没有。希望下周还能做出三道。
leetcode 57/100