题目：

95. 不同的二叉搜索树 II

题解：

题解1：

题解2：

我们可以利用一下查找二叉树的性质。左子树的所有值小于根节点，右子树的所有值大于根节点。

所以如果求 1…n 的所有可能。

我们只需要把 1 作为根节点，[ ] 空作为左子树，[ 2 … n ] 的所有可能作为右子树。

2 作为根节点，[ 1 ] 作为左子树，[ 3…n ] 的所有可能作为右子树。

3 作为根节点，[ 1 2 ] 的所有可能作为左子树，[ 4 … n ] 的所有可能作为右子树，然后左子树和右子树两两组合。

4 作为根节点，[ 1 2 3 ] 的所有可能作为左子树，[ 5 … n ] 的所有可能作为右子树，然后左子树和右子树两两组合。

…

n 作为根节点，[ 1… n ] 的所有可能作为左子树，[ ] 作为右子树。

至于，[ 2 … n ] 的所有可能以及 [ 4 … n ] 以及其他情况的所有可能，可以利用上边的方法，把每个数字作为根节点，然后把所有可能的左子树和右子树组合起来即可。

如果只有一个数字，那么所有可能就是一种情况，把该数字作为一棵树。而如果是 [ ]，那就返回 null。

题解3：

代码：


/** * code95 */

import java.util.*;

public class code95 {

    public static List<TreeNode> generateTrees(int n) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        if (n == 0) {
            return ans;
        }
        return getAns(1, n);
    }

    public static List<TreeNode> getAns(int start, int end) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        // 此时没有数字，将 null 加入结果中
        if (start > end) {
            ans.add(null);
            return ans;
        }
        // 只有一个数字，当前数字作为一棵树加入结果中
        if (start == end) {
            TreeNode tree = new TreeNode(start);
            ans.add(tree);
            return ans;
        }
        // 尝试每个数字作为根节点
        for (int i = start; i <= end; i++) {
            // 得到所有可能的左子树
            List<TreeNode> leftTrees = getAns(start, i - 1);
            // 得到所有可能的右子树
            List<TreeNode> rightTrees = getAns(i + 1, end);
            // 左子树右子树两两组合
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    // 加入到最终结果中
                    ans.add(root);
                }
            }
        }
        return ans;
    }

    // public static void main(String[] args) {
    // Scanner sc = new Scanner(System.in);
    // while (sc.hasNextInt()) {
    // int n = sc.nextInt();
    // List<TreeNode> list = generateTrees(n);
    // for (int i = 0; i < list.size(); i++) {
    // TreeNode tree = list.get(i);
    // List<List<Integer>> res = levelOrder(tree);
    // for (int j = 0; j < res.size(); j++) {
    // List<Integer> ll = res.get(j);
    // for (int k = 0; k < ll.size(); k++) {
    // System.out.print(ll.get(k) + " ");
    // }
    // }
    // System.out.println();
    // }
    // System.out.println("请继续进行输入：");
    // }
    // }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            List<TreeNode> list = generateTrees(n);
            System.out.printf("以 1 ... %d 为节点组成的二叉搜索树有%d种\n", n, list.size());
            System.out.println("***************************************");
            for (int i = 0; i < list.size(); i++) {
                TreeNode tree = list.get(i);
                TreeOperation.show(tree);
                System.out.println("***************************************");
            }
            System.out.println("请继续进行输入：");
        }
    }
}

95. 不同的二叉搜索树 II

题目：

题解：

题解1：

题解2：

题解3：

代码：

参考：