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

[balabala] 递归函数中当beg > end时要往结果中添加一个null元素，不然上一层for循环始终不能执行，从而导致最终结果总为空。

被yb君指正，发现自己对各算法特点并不熟悉，复习了下，关于分治下面链接非常好
http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html
分治法所能解决的问题一般具有以下几个特征：
    1) 该问题的规模缩小到一定的程度就可以容易地解决
    2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
    3) 利用该问题分解出的子问题的解可以合并为该问题的解；
    4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; left = null; right = null; }
* }
*/
public class Solution {
    public List generateTrees(int n) {
        ArrayList trees = new ArrayList();
        recur(1, n, trees);
        return trees;
    }
    
    public void recur(int beg, int end, ArrayList trees) {
        if (beg > end) {
            trees.add(null);
            return;
        }
        else if (beg == end) {
            TreeNode tree = new TreeNode(beg);
            trees.add(tree);
            return;
        }
        for (int root = beg; root  leftSubTrees = new ArrayList();
            recur(beg, root - 1, leftSubTrees);
            ArrayList rightSubTrees = new ArrayList();
            recur(root + 1, end, rightSubTrees);
            for (TreeNode left : leftSubTrees) {
                for (TreeNode right : rightSubTrees) {
                    TreeNode treeRoot = new TreeNode(root);
                    treeRoot.left = left;
                    treeRoot.right = right;
                    trees.add(treeRoot);
                }
            }
        }
    }
}

 

 

评论

2 楼 likesky3 2015-04-22  

leetcode中是归在动态规划类中的，自己就这么被忽悠了，最后还是得怪自己本事没学到家，分辨力不够

1 楼 qb_2008 2015-04-21  

这是分治法，不是动态规划，不过解空间就是O(n^n)的，应该只能分治。