Unique Binary Search Trees
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.
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
Analysis:
DP works well in this problem.
For each sequence from 1 to n, # of BSTs equals:
Sum of BSTs where each number (from 1 to n) is considered as the root node.
For each node, # of BSTs equals:
# of bsts of its left child times # of bsts of its right child.
Denote bst[i] = the number of BSTs can be constructed that store values from 1..n.
n = 1, Node = {1}, bst[1] = 1
n = 2, Node = {1, 2}
when 1 is the root node, there is 1 bst
1
\
2
when 2 is the root node, there is 1 bst
2
/
1
bst[2] = 2
n = 3, Node = {1, 2, 3}
when 1 is the root node, bst[3] = bst[3] + bst[2] where stores 2 values (2 and 3)
1 1 1
\ = \ \
BSTs of {2,3} 2 3
\ /
3 2
when 2 is the root node, bst[3] = bst[3] + bst[1] + bst[1]
2
/ \
1 3
when 3 is the root node, bst[3] = bst[3] + bst[2] where stores 2 values (1 and 2)
3 3 3
/ = / /
BSTs of {1,2} 2 1
/ \
1 2
For each sequence from 1 to n, # of BSTs equals:
Sum of BSTs where each number (from 1 to n) is considered as the root node.
For each node, # of BSTs equals:
# of bsts of its left child times # of bsts of its right child.
Denote bst[i] = the number of BSTs can be constructed that store values from 1..n.
n = 1, Node = {1}, bst[1] = 1
n = 2, Node = {1, 2}
when 1 is the root node, there is 1 bst
1
\
2
when 2 is the root node, there is 1 bst
2
/
1
bst[2] = 2
n = 3, Node = {1, 2, 3}
when 1 is the root node, bst[3] = bst[3] + bst[2] where stores 2 values (2 and 3)
1 1 1
\ = \ \
BSTs of {2,3} 2 3
\ /
3 2
when 2 is the root node, bst[3] = bst[3] + bst[1] + bst[1]
2
/ \
1 3
when 3 is the root node, bst[3] = bst[3] + bst[2] where stores 2 values (1 and 2)
3 3 3
/ = / /
BSTs of {1,2} 2 1
/ \
1 2
Code(C++):
class Solution { public: int numTrees(int n) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<int> table(n+1,0); if (n==0){return 0;} table[0]=1; table[1]=1; table[2]=2; for (int i=3;i<=n;i++){ int res=0; for (int j=0;j<=i-1;j++){ res = res+ table[j]*table[i-1-j]; } table[i]=res; } return table[n]; } };
Code(Python):
class Solution: # @return an integer def numTrees(self, n): if n <= 1: return 1 res = [0 for x in range(n + 1)] res[0] = 1 res[1] = 1 i = 2 while i <= n : for j in xrange(i): res[i] = res[i] + res[j]* res[i-j-1] i = i + 1 return res[n]
No comments:
Post a Comment