Massive Algorithms: LeetCode 96 - Unique Binary Search Trees I

喜刷刷: [LeetCode] Unique Binary Search Trees I, II
Related: LeetCode 95 - Unique Binary Search Trees II

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

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

https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i)

The computation can be simplified even more based on symmetry.

int numTrees(int n) { int nums[2000]={1,1,}; int i,x; for(x=2;x<=n;x++){ for(i=1;i<=x/2;i++) nums[x]=nums[x]+nums[i-1]*nums[x-i]; if(x%2==0)nums[x]=2*nums[x]; else nums[x]=2*nums[x]+nums[x/2]*nums[x/2]; } return nums[n]; }

G(n): the number of unique BST for a sequence of length n.

F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.

As one can see, G(n) is the actual function we need to calculate in order to solve the problem. And G(n) can be derived from F(i, n), which at the end, would recursively refer to G(n).

First of all, given the above definitions, we can see that the total number of unique BST G(n), is the sum of BST F(i) using each number i as a root. i.e.

G(n) = F(1, n) + F(2, n) + ... + F(n, n).

Particularly, the bottom cases, there is only one combination to construct a BST out of a sequence of length 1 (only a root) or 0 (empty tree). i.e.

G(0)=1, G(1)=1.

Given a sequence 1…n, we pick a number i out of the sequence as the root, then the number of unique BST with the specified root F(i), is the cartesian product of the number of BST for its left and right subtrees. For example, F(3, 7): the number of unique BST tree with number 3 as its root. To construct an unique BST out of the entire sequence [1, 2, 3, 4, 5, 6, 7] with 3 as the root, which is to say, we need to construct an unique BST out of its left subsequence [1, 2] and another BST out of the right subsequence [4, 5, 6, 7], and then combine them together (i.e.cartesian product). The tricky part is that we could consider the number of unique BST out of sequence [1,2] as G(2), and the number of of unique BST out of sequence [4, 5, 6, 7] as G(4). Therefore, F(3,7) = G(2) * G(4).

i.e.

F(i, n) = G(i-1) * G(n-i)   1 <= i <= n

Combining the above two formulas, we obtain the recursive formula for G(n). i.e.

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)

In terms of calculation, we need to start with the lower number, since the value of G(n) depends on the values of G(0) … G(n-1).

public int numTrees(int n) {
    int [] G = new int[n+1];
    G[0] = G[1] = 1;
    
    for(int i=2; i<=n; ++i) {
     for(int j=1; j<=i; ++j) {
      G[i] += G[j-1] * G[i-j];
     }
    }

    return G[n];
}

定义f(n)为unique BST的数量，以n = 3为例：

构造的BST的根节点可以取{1, 2, 3}中的任一数字。

如以1为节点，则left subtree只能有0个节点，而right subtree有2, 3两个节点。所以left/right subtree一共的combination数量为：f(0) * f(2) = 2

以2为节点，则left subtree只能为1，right subtree只能为2：f(1) * f(1) = 1

以3为节点，则left subtree有1, 2两个节点，right subtree有0个节点：f(2)*f(0) = 2

f(0) = 1

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)

http://yuanhsh.iteye.com/blog/2175677

There are five distinct shapes of binary trees with three nodes:

But how many are there for n nodes?

Let C(n) be the number of distinct binary trees with n nodes. This is equal to the number of trees that have a root, a left subtree with j nodes, and a right subtree of (n-1)-j nodes, for each j. That is,

    C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0)

which is

The first few terms:

    C(0) = 1
    C(1) = C(0)C(0) = 1
    C(2) = C(0)C(1) + C(1)C(0) = 2
    C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 5
    C(4) = C(0)C(3) + C(1)C(2) + C(2)C(1) + C(3)C(0) = 14

You can prove

Here's the number of 8-node binary trees:

           1   16!    16×15×14×13×12×11×10
    C(8) = - × ---- = -------------------- = 13×11×10 = 1430
           9   8!8!      8×7×6×5×4×3×2×1

Also see Wikipedia's article on the Catalan Numbers.

通过以上分析可用DP解决。

public int numTrees(int n) {
if(n<=1) return 1;
int[] c = new int[n+1];
c[0]=c[1]=1;
for(int i=2; i<=n; i++) {
for(int j=0; j<i; j++) {
c[i] += c[j]*c[i-j-1];
}
}
return c[n];
}

https://leetcode.com/discuss/61053/9-line-clean-java-dp-solution

public int numTrees(int n) { if (n < 2) return n; int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { int sum = 0; for (int j = 0; j < i; j++) sum += dp[j] * dp[i - j - 1];//\\ dp[i] = sum; } return dp[n]; }

https://leetcode.com/discuss/17674/dp-problem-10-lines-with-comments

If input n is 0, then dp[1] would be out ouf range

X. http://www-math.mit.edu/~rstan/ec/catalan.pdf

根据Catalan Number的Fourth Proof,

(4n+2)C_n = (n+2)C_{n+1}.

那么,

(4n-2)Cn-1 = (n+1)Cn,

也就是：

Cn = Cn-1(4n-2)/(n+1)

http://en.wikipedia.org/wiki/Catalan_number

public int numTrees(int n) {
if(n<=1) return 1;
int res = 1;
for(int i=1; i<=n; i++) {
res = res*(4*i-2)/(i+1);
}
return res;
}

http://n00tc0d3r.blogspot.com/2013/07/unique-binary-search-trees.html

Think it in a deductive way:

n=1, count(1) = 1 unique BST.
n=2, pick one value, and the one remaining node can be built as one BST.
i.e. count(2) = 2 * count(2-1).
n=3, pick one value i, and split the remaining values to two groups: [1 .. i-1] goes to left subtree and [i+1 .. n] goes to right subtree.
i.e. count(3) = count(3-1) + count(1)*count(1) + count(3-1)
... ...
n=k, suppose count(0) = 1, we then have:

count(k) = sum_{i=0}^(k-1) (count(i)*count(k-1-i))

This problem can be reduced to finding the total number of structurally unique binary tree with n nodes, which can then be reduced to Euler's Polygon Division Problem. The result of the above recurrence formula gives the Catalan number such that

count(n) = Combination(2n, n) - Combination(2n, n+1) = (2n)! / ((n+1)!n!)'

time O(n) with O(1) spaces:

 public int numTrees(int n) {  
   if (n == 0) return 0;  
   int count = 1;  
   
   for (int i=2; i<=n; ++i) {  
     count *= ((2*i - 1) / (i+1));  
   }  
   
   return count;  
 }

X. DFS + cache
https://leetcode.com/discuss/26660/simple-recursion-java-solution-with-explanation

The idea is to use each number i as root node, then the left branch will be what's less than i, the right branch will be what's larger than i. The total number of distinct structure is their product. Thus, sum up the product for all numbers. Use a map to memorize the visited number.

The original DFS solution will run in O(2^n) time. When apply path memorizing, the DFS will run in O(n^2) time.
public int numTrees(int n) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(0,1); map.put(1,1); return numTrees(n, map); } private int numTrees(int n, Map<Integer, Integer> map){ // check memory if(map.containsKey(n)) return map.get(n); // recursion int sum = 0; for(int i = 1;i <= n;i++) sum += numTrees(i-1, map) * numTrees(n-i, map); map.put(n, sum); return sum; }
Use array as DP cache:
public int numTrees(int n) { // base case if(n <= 1){return 1;} if (memo[n] != -1) return memo[n]; // recursion int sum = 0; for(int i = 1;i <= n;i++) sum += numTrees(i-1-0) * numTrees(n-i); return memo[n] = sum; }
Read full article from 喜刷刷: [LeetCode] Unique Binary Search Trees I, II

LeetCode 96 - Unique Binary Search Trees I

Labels

Popular Posts