# 95. Unique Binary Search Trees II

{% hint style="danger" %}
不是很懂为什么在`helper`函数的开头要定义一个空的`bst`数组? 有点难做，需要再练习来加强。

`subTree(start, end)` 是在区间`[start, end]`中找出所有的解法，那么就是移动`root`，`root = [start: end]`，返回值是一个叫`bst`的`list`，存放所有解法的`TreeNode(root)`树结构。
{% endhint %}

![用两层循环针对当前的root来构建新的bst](/files/-MASL22RjC_R3-xhN_Ks)

### Solution:

1. 由于每次递归时，`bst`都是新的，因此helper函数的开头新建了一个空`bst`；
2. `root`左边有`n`个解法，`root`右边有`m`个解法，那么一共就有`n*m`个解法，所以一定要用两层嵌套的for循环得到新的`bst`；
3. helper函数中的终止条件要注意，当`start>end`时才终止，这时候一定要加上`NULL`，不然那么多`NULL`哪里加呢。这一点是最难想清楚的。

{% tabs %}
{% tab title="First Tab" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:     
        # edge case
        if n == 0:
            return []

        return self.subTree(1, n)
    
    # bst -> List[TreeNode]
    # bst[i] means when (root = i-1), all possible BST
    def subTree(self, start, end): 
        # stop condition
        bst = []
        if start > end:
            bst.append(None)
            return bst
        
        # regular case
        for i in range(start, end+1):
            left = self.subTree(start, i-1)
            right = self.subTree(i+1, end)
            for x in left:
                for y in right:
                    root = TreeNode(i)
                    root.left = x
                    root.right = y
                    bst.append(root)
        return bst
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}

Time complexity: $$f\_i=\sum(f\_{i-1})\*\sum(f\_{n-i})$$ 很难算，空间复杂度是一样的。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://r24zeng.gitbook.io/leetcode-notebook/binary-search-and-tree/95.-unique-binary-search-trees-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.