栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

leetcode1382. 将二叉搜索树变平衡

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

leetcode1382. 将二叉搜索树变平衡

题目描述

给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法,请你返回任意一种。

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

题解
class Solution {
    List orderList = new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        getOrderList(root);
        return buildBalanceBST(0, orderList.size() - 1);
    }
    public void getOrderList(TreeNode node) {
        if(node == null) {
            return;
        }
        getOrderList(node.left);
        orderList.add(node.val);
        getOrderList(node.right);
    }
    public TreeNode buildBalanceBST(int l, int r) {
        int mid = (l + r) >> 1;
        TreeNode root = new TreeNode(orderList.get(mid));
        if(l <= mid - 1) {
            root.left = buildBalanceBST(l, mid - 1);
        }
        if(r >= mid + 1) {
            root.right = buildBalanceBST(mid + 1, r);
        }
        return root;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/957264.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号