I am giving a binary search tree with n node with unique value 1 to n and need to compute how many structurally different binary search tree I can make from it. I use DFS with memoization to solve the problem. It is basically like if we have n node, the root node can be from 1 to n, then I recursively compute how many the subtree can the tree has. Also, I memoized the range of node value the tree can have and how many different tree can be made with that range of node value, so I dont recompute. I think the Time and Space are both O(n^2) as there can be n^2 different range for my tree node val. Can anyone comment on that?
class Solution {
public int numTrees(int n) {
// structrually unique BST with value from 1 to n
// same structure but different number? no, one way to arrange node
// from 1 to n start
// left has num candid - 1 to 1
// right has num candid 1 to n
Map<Integer, Integer> memo = new HashMap<>();
return numWays(1, n, memo);
}
private int numWays(int low, int high, Map<Integer, Integer> memo) {
if(memo.containsKey(low * 100 high)) {
return memo.get(low * 100 high);
}
if(low >= high) return 1;
int ans = 0;
for(int i = low; i <= high; i ) {
ans = ans numWays(low, i - 1, memo) * numWays(i 1, high, memo);
}
memo.put(low * 100 high, ans);
return ans;
}
}
CodePudding user response：
The time complexity is currently O(n^3). It is true that there are only O(n^2) ranges, and at most O(n^2) pairs of (low, high) appearing as inputs to the numWays function. However, the numWays function takes O(high-low 1) steps after memoization, which is another O(n) factor.
To speed this up, you might notice that the number of BST's for [1,2,3,4] is the same as the number of BST's for [2,3,4,5] or for [3,4,5,6]; only the length of the array matters (giving you an O(n^2) algorithm from a tiny change). Another possible speedup comes from noticing that for every rooted binary tree with n nodes, there is exactly one way to label the nodes with [1,2,...,n] to get a BST, so you're looking for a way/recurrence to count rooted binary trees.
CodePudding user response：
We could also use a formula:
const f = n => n < 2 ? 1 : (4*n - 2) / (n 1) * f(n - 1);
for (let i=0; i<20; i )
console.log(f(i));