leetcode Unique Binary Search Trees II

这道题如下：

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3

开始拿到这道题，想到用backtracing。当时考虑，只要求出n个数的所有排列组合的情况，对每一种情况，
例如1,3,5,4,2。只要依次插入这些元素，就可以得到一颗BST。遍历完所有的情况，即可得出解。然而稍微考虑了一下，这个方法肯定是不对的。
比如上面这个例子，当n=3的时候，全排列一共有6种情况，然而只有5颗不同的BST，说明在必定有多对一的情况。

再次考虑，如果我有n-1情况下所有的BST，那么我能否由此推出n情况下所有的BST？
答案是可以的，例如，当n=2的时候，很显然，只有2种情况，即
 2      1    
/        
1         2
那么，当n=3时，只需对两种情况分别插入3即可。那么这个3插入在哪里？
以情况2为例子，3可以插入在根节点，即以3为根节点，原来的树作为其右子树，
即
3

  1

　　2
还有一种可能是插入到1的右子树，因为n肯定比当前树的所有结点都大，所以他不可能出现在左子树。
那么插入到右子树有两种情况，
1          1

  3          2

    2          3
以此类推，不断迭代出所需的结果。
然而，这个方法超时了。
上网查了一个新的方法，原理很简单，就是以不同的数作为根节点，然后迭代其左右子树。
给出代码：

public class Solution4 {
    public ArrayList<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }
 
    public ArrayList<TreeNode> generateTrees(int start, int end){
        ArrayList<TreeNode> unique = new ArrayList<TreeNode>();
        if(start > end){
            unique.add(null);
            return unique;
        }
        for(int i = start; i <= end; i++){
            for(TreeNode left: generateTrees(start, i - 1)){
                for(TreeNode right: generateTrees(i + 1, end)){
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    unique.add(root);
                }
            }
        }
        return unique;
    }      
}

leetcode Unique Binary Search Trees II

相关推荐