LeetCode 1382. 将二叉搜索树变平衡

Categories:

题目描述
思路分析
1. 解法一：中序 + 递归构建（推荐）
相似题目

题目描述

✅ 1382. 将二叉搜索树变平衡

思路分析

解法一：中序 + 递归构建（推荐）

核心思路：

中序遍历 BST 得到有序数组。

选择数组中点作为根，递归构建左右子树，保证平衡。

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(n)。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        inorder(root, vals);
        return build(vals, 0, vals.size() - 1);
    }

    private void inorder(TreeNode node, List<Integer> vals) {
        if (node == null) {
            return;
        }
        inorder(node.left, vals);
        vals.add(node.val);
        inorder(node.right, vals);
    }

    private TreeNode build(List<Integer> vals, int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = l + (r - l) / 2;
        TreeNode root = new TreeNode(vals.get(mid));
        root.left = build(vals, l, mid - 1);
        root.right = build(vals, mid + 1, r);
        return root;
    }
}

func balanceBST(root *TreeNode) *TreeNode {
    vals := make([]int, 0)
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        vals = append(vals, node.Val)
        inorder(node.Right)
    }
    inorder(root)

    var build func(int, int) *TreeNode
    build = func(l, r int) *TreeNode {
        if l > r {
            return nil
        }
        mid := l + (r-l)/2
        node := &TreeNode{Val: vals[mid]}
        node.Left = build(l, mid-1)
        node.Right = build(mid+1, r)
        return node
    }

    return build(0, len(vals)-1)
}

相似题目

题目	难度	考察点
108. 将有序数组转换为二叉搜索树	简单	分治
109. 有序链表转换二叉搜索树	中等	分治
669. 修剪二叉搜索树	中等	BST
538. 把二叉搜索树转换为累加树	中等	BST
701. 二叉搜索树中的插入操作	中等	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/63975794