96. 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.

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

S: DP

第n个元素是所有元素最大的，其他n-1个元素只可能出现在它的左子树或者父节点（n为最右节点）

    int numTrees(int n) {
        if(n == 0) return 0; 
        vector<int> result(n+1, 0);
        result[0] = result[1] = 1;
        for(int i = 2; i <= n; ++i) {
            for(int j = 0; j < i; ++j) {
                result[i] += result[j]*result[i-1-j];
            }
        }
        return result[n];
    }

95. Unique Binary Search Trees II

Given an integer 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

S: recursion

对于任意数字i作为root，左子树一定全部小于root(1到i-1)，右子树全部大于root(i+i到n)

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0) return vector<TreeNode*> {}; 
        return genTreeHelper(1, n);
    }

    vector<TreeNode*> genTreeHelper(int start, int end) {
        if(start > end) return vector<TreeNode*>{NULL};//这里不能返回空数组
        vector<TreeNode*> result;
        for(int i = start; i <= end; ++i) {
            vector<TreeNode*> leftNodes = genTreeHelper(start, i-1);
            vector<TreeNode*> rightNodes = genTreeHelper(i+1, end);
            for(auto left: leftNodes) {
                for(auto right: rightNodes) {
                    TreeNode* node = new TreeNode(i);
                    node->left = left;
                    node->right = right;
                    result.push_back(node);
                }
            }
        }
        return result;
    }
};