[LeetCode] Unique Binary Search Trees I && II

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);
                    }
                }
            }
        }
    }
};