https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

原题

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

代码

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public List<TreeNode> generateTrees(int n) {
    if (n == 0) {
        return new ArrayList<>();
    }
    return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int start,int end) {
    List<TreeNode> treeNodes = new ArrayList<>();
    
    // 没有符合条件的节点
    if (start > end) {
    	// 添加null,否则循环走不下去
        treeNodes.add(null);
        return treeNodes;
    }
    // 构建以i为根节点的互不相同的二叉搜索树
    for (int i = start; i < end + 1; i++) {
        // 找到所有符合条件的左子树
        List<TreeNode> leftTrees = generateTrees(start, end - 1);
        // 找到所有符合条件的右子树
        List<TreeNode> rightTrees = generateTrees(start + 1, end);
        // 遍历得到所有左右子树的排列组合
        for (TreeNode leftTree : leftTrees) {
            for (TreeNode rightTree : rightTrees) {
                // 构建根节点
                TreeNode treeNode = new TreeNode(i,leftTree,rightTree);
                treeNodes.add(treeNode);
            }
        }
    }
    return treeNodes;
}