21 unique-binary-search-trees-ii

题目描述

给定一个值n,请生成所有的存储值1…n.的二叉搜索树（BST）的结构
例如：
给定n=3，你的程序应该给出下面五种不同的二叉搜索树（BST）
思路:

【分析】
比如，以 1 为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是 0 个元素的树，右子树是 2 个元素的树。

以 2 为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是 1个元素的树，右子树也是 1 个元素的树。依此类推。
当数组为 1; 2; 3; …..; n 时，基于以下原则的构建的 BST 树具有唯一性：以 i 为根节点的树，其左子树由 [1, i-1] 构成，其右子树由 [i+1, n] 构成。
定义 f (i) 为以 [1; i] 能产生的 Unique Binary Search Tree 的数目，则
如果数组为空，毫无疑问，只有一种 BST，即空树，f (0) = 1。
如果数组仅有一个元素 1，只有一种 BST，单个节点，f (1) = 1。
如果数组有两个元素 1,2，那么有如下两种可能

f (2) = f (0) f (1) ，1 为根的情况
+ f (1) f (0) ， 2 为根的情况

再看一看 3 个元素的数组，可以发现 BST 的取值方式如下：
f (3) = f (0) f (2) ，1 为根的情况
+ f (1) f (1) ，2 为根的情况
+ f (2) * f (0) ，3 为根的情况

所以，由此观察，可以得出 f 的递推公式为

至此，问题划归为一维动态规划。

//找二叉树的个数
public static int numTree(int n) {
        if(n>1) {
            int[] sum = new int[n+1];
            sum[0] = 1;
            sum[1] = 1;
            for(int i=2;i<=n;i++) {
                for(int k=1;k<=i;k++) {
                    sum[i] += sum[k-1]*sum[i-k]; 
                }
            }
            return sum[n];
        }else {
            return 1;
        }
    }

//给定n值生成二叉树
    public ArrayList<TreeNode> generateTrees (int n) {        
        ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
        if(n==0) {
            arr.add(null);
            return arr;
        }        
        return iterTree(1,n);
        // write code here
    }
    public ArrayList<TreeNode> iterTree(int start,int end){
        ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
        if(start>end) {
            arr.add(null);
            return arr;
        }
        for(int i = start;i<=end;i++) {
            ArrayList<TreeNode> left = iterTree(start, i-1);
            ArrayList<TreeNode> right = iterTree(i+1, end);
            for(TreeNode leftNode:left) {
                for(TreeNode rightNode:right) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    arr.add(root);
                }
            }
         }
        return arr;
    }