For todays leetcode challenge Unique Binary Search Trees II. This is the dp solution. I think it has best possible run time. But I don't even have a clue on how to figure out its run time. Here is what I think. At each level we are doing O(N) work then two recursive calls .. combined these two calls will inturn recursively call N-1 times .. till 1 element is left.. thus estimate is it is N^N roughly..
am I correct? What is your reasoning on this..
class Solution {
List<TreeNode>[][] dp;
public List<TreeNode> generateTrees(int n) {
dp = new List[n+1][n+1];
return solution(1, n);
}
public List<TreeNode> solution(int lo, int hi){
List<TreeNode> res= new ArrayList<TreeNode>();
if(lo>hi){
res.add(null);
return res;
}
if(lo==hi){
res.add(new TreeNode(lo));
return res;
}
if(dp[lo][hi]!=null)
return dp[lo][hi];
for(int i=lo; i<=hi; i++){
List<TreeNode> left_roots = solution(lo, i-1);
List<TreeNode> right_roots = solution(i+1, hi);
for(TreeNode left_h : left_roots){
for(TreeNode right_h : right_roots){
TreeNode root = new TreeNode(i);
root.left = left_h;
root.right = right_h;
res.add(root);
}
}
}
dp[lo][hi] = res;
return res;
}
}Comments (0)