题目

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 8

题解

public List<TreeNode> generateTrees(int n) {
    BiFunction<Integer, Integer, List<TreeNode>> generate = new BiFunction<Integer, Integer, List<TreeNode>>() {
        @Override
        public List<TreeNode> apply(Integer start, Integer end) {
            List<TreeNode> list = new ArrayList<>();
            if (start > end) {
                list.add(null);
                return list;
            }

            for (int i = start; i <= end; i++) {
                // 构造左二叉搜索树
                List<TreeNode> leftTrees = this.apply(start, i - 1);
                // 构造右二叉搜索树
                List<TreeNode> rightTrees = this.apply(i + 1, end);
                // 组合成二叉树
                for (TreeNode left : leftTrees) {
                    for (TreeNode right : rightTrees) {
                        TreeNode root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        list.add(root);
                    }
                }
            }

            return list;
        }
    };

    return n == 0 ? new ArrayList<>() : generate.apply(1, n);
}