# 96. Unique Binary Search Trees

## 1.問題

* 給一個n, 計算有多少BST組合

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LK9gDw4LldRDG5ciiQn%2F-LK9sRaG5BrC4w8T3V6M%2F20180818.jpg?alt=media\&token=edbe3a7b-9270-4bce-8cf9-57123b0abd62)

## 2.想法

* When the number of nodes is 1 there is just one possible tree- this is the base case
* Consider that every node can be the root - the nodes before it will be on the left and the nodes after it on the right

## 3.程式碼

```
class Solution {
public:
    int numTrees(int n) {
        vector<int> v(n + 1, -1);
        return numTreesCount(n, v);
    }
private:
    int numTreesCount(int n, vector<int>& v) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (v[n] != -1) {
            return v[n]; 
        }
        
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int left = numTreesCount(i - 1, v);
            int right = numTreesCount(n - i, v);
            sum = sum + left * right;
        }
        v[n] = sum;
        return sum;
    }
};
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LK9tyj-9xqz7rz8YtMH%2F-LK9xhB9-NvlJ-P1XFVq%2F2018081801.jpg?alt=media\&token=7ea1e860-976d-490d-bd36-96eb9851dc3a)