前序遍历构造二叉搜索树

/*
 * 思路：
 * 1. 使用 Java Stream 构造二叉搜索树。
 * 2. 前序遍历数组的第一个元素是树的根节点。
 * 3. 使用流的分区功能将元素分为比根节点小的左子树和比根节点大的右子树。
 * 4. 递归地构造左子树和右子树。
 */

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

public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode bstFromPreorder(int[] preorder) {
        return constructBST(Arrays.stream(preorder).boxed().collect(Collectors.toList()));
    }

    private TreeNode constructBST(List<Integer> preorder) {
        if (preorder.isEmpty()) return null;
        TreeNode node = new TreeNode(preorder.get(0));
        List<Integer> leftSubtree = preorder.stream().skip(1).filter(x -> x < node.val).collect(Collectors.toList());
        List<Integer> rightSubtree = preorder.stream().skip(1).filter(x -> x > node.val).collect(Collectors.toList());
        node.left = constructBST(leftSubtree);
        node.right = constructBST(rightSubtree);
        return node;
    }
}