Leetcode | Unique Binary Search Trees I && II

Unique Binary Search Trees I

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

Method I

递归就可以解。每次取出第i个数作为root，[0...i - 1]作为左子树，[i+1...n-1]作为右子树。

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

Method II

动态规划。这其实是一个卡特兰数的例子。和Generate Parentheses类似。

 1 class Solution {
 2 public:
 3     
 4     int numTrees(int n) {
 5         vector<int> count(n + 1, 0);
 6         count[0] = count[1] = 1;
 7         
 8         for (int i = 2; i <= n; ++i) {
 9             for (int j = 0; j < i; ++j) {
10                 count[i] += count[j] * count[i - j - 1];
11             }
12         }
13         return count[n];
14     }
15 };

Unique Binary Search Trees II

递归，虽然结果很多，但是没办法。从[s,e]中取出第i个数，以[s,i-1]构建左子树，以[i+1,e]构建右子树。组合一下。

 1 class Solution {
 2 public:
 3     vector<TreeNode*> generateTrees(int n) {
 4         return recursive(1, n);
 5     }
 6     
 7     vector<TreeNode*> recursive(int s, int e) {
 8         vector<TreeNode *> ret;
 9         if (s > e) {
10             ret.push_back(NULL);
11             return ret;
12         }
13         
14         for (int i = s; i <= e; ++i) {
15             vector<TreeNode *> lefts = recursive(s, i - 1);
16             vector<TreeNode *> rights = recursive(i + 1, e);
17             for (int j = 0; j < lefts.size(); ++j) {
18                 for (int k = 0; k < rights.size(); ++k) {
19                     TreeNode* root = new TreeNode(i);
20                     root->left = lefts[j];
21                     root->right = rights[k];
22                     ret.push_back(root);
23                 }
24             }
25         }
26         return ret;
27     }
28 };