# 96. Unique Binary Search Trees

### Leetcode

<https://leetcode.com/problems/unique-binary-search-trees/>

### 題目

Given an integer `n`, return *the number of structurally unique **BST'**&#x73; (binary search trees) which has exactly* `n` *nodes of unique values from* `1` *to* `n`.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg)

<pre><code><strong>Input: n = 3
</strong><strong>Output: 5
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: n = 1
</strong><strong>Output: 1
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

這一題其實跟前一題 95. 一模一樣，差別在前一題要求出整個樹狀結構，但這一題只需要求出數量就好，所以我們可以使用 95. 題中遞迴的解法，改成回傳數量就是這題要的答案

```javascript
var numTrees = function (n) {
    const checkNumTrees = (start, end) => {
        let totalNums = 0;

        if (start > end) {
            return 1;
        }
        if (start === end) {
            return 1;
        }

        for (let i = start; i <= end; i++) {
            const leftTreeNums = checkNumTrees(start, i - 1);
            const rightTreeNums = checkNumTrees(i + 1, end);
            
            // 左右子樹的數量相配對後，再加進來
            totalNums += leftTreeNums * rightTreeNums;
        }

        return totalNums;
    }

    return checkNumTrees(1, n);
};
```

更進一步來看，由於這題只需要求 BST 的數量，因此 `const leftTreeNums = checkNumTrees(start, i - 1);` 這行實際上不用傳入 start 跟 end 的數值，只需要傳入節點的數量就可以，例如：`start=1, end=3` => 總共有五種組合，換成 `start=5, end=7` 一樣也是五種組合

因此以上可以改寫為：

```javascript
var numTrees = function (n) {
    const checkNumTrees = (n) => {
        let totalNums = 0;

        // 0 個或 1 個節點都回傳 1
        if (n === 0 || n === 1) {
            return 1;
        }

        for (let i = 1; i <= n; i++) {
            const leftTreeNums = checkNumTrees(i - 1);
            const rightTreeNums = checkNumTrees(n - i);

            totalNums += leftTreeNums * rightTreeNums;
        }

        return totalNums;
    }

    return checkNumTrees(n);
};
```

雖然這個解法的方向是對的，但實際跑時會發現當 `n` 太大時導致了 Time Limit Exceeded

所以我們需要能夠快取節點的數量，就像上面提到只要 `checkNumTrees` 函式傳入的 `n` 是一樣的，回傳的 `totalNums` 也會是一樣的數值

```javascript
var numTrees = function (n) {
    // 利用 map 快取 n 與樹狀結構總數的關係
    const map = {};

    const checkNumTrees = (n) => {
        if (n in map) {
            return map[n];
        }

        let totalNums = 0;

        if (n === 0 || n === 1) {
            return 1;
        }

        for (let i = 1; i <= n; i++) {
            const leftTreeNums = checkNumTrees(i - 1);
            const rightTreeNums = checkNumTrees(n - i);

            totalNums += leftTreeNums * rightTreeNums;
        }

        map[n] = totalNums;

        return totalNums;
    }

    return checkNumTrees(n);
};
```

Runtime: 47 ms Beats 75.77% of users with JavaScript

Memory: 48.96 MB Beats 20.14% of users with JavaScript
