# 95. Unique Binary Search Trees II

### Leetcode

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

### 題目

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

&#x20;

**Example 1:**

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

<pre><code><strong>Input: n = 3
</strong><strong>Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
</strong></code></pre>

**Example 2:**

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

### **前置知識**

Binary Search Tree (BST) 是一種符合以下幾種特性的資料結構：

1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
3. 任意節點的左、右子樹也分別為二元搜尋樹；

簡單來說就是 **樹的左邊比根節點小**，**數的右邊比根節點大**

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

* **方法一 - 遞迴**

要求出從 `1~n` 所有可能的 BST，如果從根節點來看的話會有以下幾種可能：

1. 根節點為 `1`：

左子樹為 `[]`，右子樹為 `[2, ..., n]` 所有可能的 BST

2. 根節點為 `2`：

左子樹為 `[1]`，右子樹為 `[3, ..., n]` 所有可能的 BST

3. 根節點為 `3`：

左子樹為 `[1, 2]`，右子樹為 `[4, ..., n]` 所有可能的 BST

............

4. 根節點為 `n`：

左子樹為 `[1, ..., n-1]`，右子樹為 `[]`

而子樹中所有可能的 BST，一樣可以按照上面的方式，先固定根節點的元素，在分成左右子樹尋找所有可能的組合

```javascript
var generateTrees = function (n) {
    const buildTrees = (start, end) => {
        const trees = [];
        
        // 沒有左邊大於右邊的子樹，所以 push null
        if (start > end) {
            trees.push(null);
            return trees;
        }

        // 單一值的節點
        if (start === end) {
            const tree = new TreeNode(start);
            trees.push(tree);
            return trees;
        }

        // 從 start 開始將所有值當作根節點
        for (let i = start; i <= end; i++) {
            // 解釋1. 建構左子樹
            const leftTrees = buildTrees(start, i - 1);
            // 解釋2. 建構右子樹
            const rightTrees = buildTrees(i + 1, end);

            // 解釋3. 將左、右子樹兩兩配對
            for (let leftTree of leftTrees) {
                for (let rightTree of rightTrees) {
                    // 將左、右子樹配對的組合放在 root 底下
                    const root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    trees.push(root);
                }
            }
        }

        return trees;
    }

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

Runtime: 73 ms Beats 64.57% of users with JavaScript

Memory: 56.48 MB Beats 60.54% of users with JavaScript

**解釋**

1. 建構左子樹

`const leftTrees = buildTrees(start, i - 1);`

假設 `start=2, i=5`，左子樹會是 `[2, 3, 4]` 組成的可能 BST

2. 建構右子樹

`const rightTrees = buildTrees(i + 1, end);`

假設 `i=2, end=5`，右子樹會是 `[3, 4, 5]` 組成的可能 BST

3. 將左、右子樹兩兩配對

假設 `[1, 2, 3, 4, 5]`，根節點為 `3`：

左子樹為 `[1, 2]`、右子樹為 `[4, 5]`，此組合下所有可能的 BST 有以下幾種：

```markup
     3            3          3           3
    / \          / \        / \         / \
   2   4        2   5      1   4       1   5
  /     \      /   /      /     \     /   /
 1       5    1   4      2       5   2   4
```

可以看到左邊是 `[1, 2]` 兩種可能性、右邊是 `[4, 5]` 兩種可能性，因此需要用雙層迴圈將左、右子樹兩兩配對後，再加入到 `root` 底下

### 參考資料

{% embed url="<https://leetcode.wang/leetCode-95-Unique-Binary-Search-TreesII.html>" %}
