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

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

1 class Solution { 2 public: 3      4     int numTrees(int n) { 5         vector
     
       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
     
       generateTrees(int n) { 4         return recursive(1, n); 5     } 6      7     vector
      
        recursive(int s, int e) { 8         vector
       
         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
        
          lefts = recursive(s, i - 1);16             vector
         
           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 };