将二叉搜索树变平衡

/*
 * 题目思路：
 * 1. 使用Java Stream收集二叉搜索树的中序遍历结果。
 * 2. 将中序遍历结果转为平衡二叉树。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public TreeNode balanceBST(TreeNode root) {
        // 使用stream收集中序遍历结果
        List<Integer> inorderList = new ArrayList<>();
        inorderTraversal(root).forEach(inorderList::add);
        // 构建平衡二叉树
        return buildBalancedTree(inorderList, 0, inorderList.size() - 1);
    }

    private Stream<Integer> inorderTraversal(TreeNode node) {
        if (node == null) return Stream.empty();
        return Stream.concat(Stream.concat(
                inorderTraversal(node.left),
                Stream.of(node.val)),
                inorderTraversal(node.right));
    }

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