Unique Binary Search Trees I
Problem Statement (
link):
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
Analysis:
At first sight, this problem seems complicated. We may get some salt if we divide the problem into smaller sub-problems.
If
n=0, there is 1 BST, which is the NULL tree.
If
n=1, there is 1 BST, which is the single root node.
If
n=2, there is 2 BST, which are BST with 1 being the root and 2 being the root.
...
We observe that for a value
k, the root node may be any
k=[1:n]. Thus, the number of BSTs in total is the number of sub-trees with node
k valued from
1 to
n.
Suppose the root node is
k, then its left sub-tree consists of all nodes less that
k, it's right sub-tree consists of all nodes larger than
k. Then number of BSTs with root node
k is then the product of number of BSTs of left sub-tree and number of BSTs of right sub-tree. Further, The number of BSTs of the left sub-tree is the number of sub-trees with the left root node valued from
1 to
k-1, the number of BSTs of the right sub-tree is the number of sub-sub-trees with the right root node valued from
k+1 to
n. Thus we could model and solve this problem with recursion.
Furthermore, if we think twice about the method, it's sort of similar to the idea of DP - having previous calculated results stored, calculate and update new results.
Code:
class Solution {
public:
int numTrees(int n) {
// count[i] - number of unique BST constructed from i nodes
vector<int> count(n+1);
count[0] = 1;
recur(count, n);
return count[n];
}
void recur(vector<int> &count, int n) {
for (int i=1; i<=n; i++) {
// k - all possible num of nodes of left subtree
for (int k=0; k<i; k++) {
count[i] += count[k]*count[i-k-1];
}
}
}
};
Unique Binary Search Trees II
Problem Statement (
link):
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
Analysis:
This problem is a bit difficult as it's not easy to come up with a clear solution.
First, the problem asks for "all" BSTs, similar to the previous problem, we consider using DFS on every possible node values, i.e., from
1 through
n.
The difficulty lies in finding a way to store each BST. The root node's value
i of a valid BST must be within
1 and
n, the root of its left subtree must be within
1 and
i-1, the root of its right subtree must be within
i+1 and
n. This idea is same as that of the previous problem. Now, suppose we have all the possible nodes stored in two vectors -
leftSub and
rightSub, in order to construct a tree, we must construct a new root node with value
i that points to a member in
leftSub and points to a member in
rightSub, respectively. Then, we push the node into our
result vector.
Codes:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
vector<TreeNode*> res;
recur(1, n, res);
return res;
}
void recur(int l, int r, vector<TreeNode*> &res) {
if (l>r)
res.push_back(NULL);
else {
for (int i=l; i<=r; i++) {
// recursively build-up left and right subtree for root node i
vector<TreeNode*> leftSub, rightSub;
recur(l, i-1, leftSub);
recur(i+1, r, rightSub);
// Choose left and right subtree combinations for root node i
for (int j=0; j<leftSub.size(); j++) {
for (int k=0; k<rightSub.size(); k++) {
TreeNode* node=new TreeNode(i);
node->left = leftSub[j];
node->right= rightSub[k];
res.push_back(node);
}
}
}
}
}
};
