# 不同的二叉搜索树 II

<div class="notranslate">
    <p>给你一个整数 <code>n</code> ，请你生成并返回所有由 <code>n</code> 个节点组成且节点值从 <code>1</code> 到 <code>n</code> 互不相同的不同
        <strong>二叉搜索树</strong><em> </em>。可以按 <strong>任意顺序</strong> 返回答案。
    </p>

    <p>&nbsp;</p>

    <div class="original__bRMd">
        <div>
            <p><strong>示例 1：</strong></p>
            <img style="width: 600px; height: 148px;"
                src="https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg" alt="">
            <pre><strong>输入：</strong>n = 3
<strong>输出：</strong>[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
    </pre>

            <p><strong>示例 2：</strong></p>

            <pre><strong>输入：</strong>n = 1
<strong>输出：</strong>[[1]]
    </pre>

            <p>&nbsp;</p>

            <p><strong>提示：</strong></p>

            <ul>
                <li><code>1 &lt;= n &lt;= 8</code></li>
            </ul>
        </div>
    </div>
</div>

## template

```python
class TreeNode(object):
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None
	def to_list(self, count):
		queue = []
		queue.append(self)
		result = []
		while len(queue) > 0:
			if count == 0:
				break
			node = queue.pop(0)
			if node is None:
				result.append('null')
			else:
				count -= 1
				result.append(node.val)
				queue.append(node.left)
				queue.append(node.right)
		return result
class Solution(object):
	def generateTrees(self, n):
		"""
		:type n: int
		:rtype: List[TreeNode]
		"""
		if n == 0:
			return []
		return self.get_trees(1, n)
	def get_trees_impl(self, start, end):
		trees = []
		if start > end:
			trees.append(None)
			return trees
		for i in range(start, end + 1):
			lefts = self.get_trees_impl(start, i - 1)
			rights = self.get_trees_impl(i + 1, end)
			for j in range(len(lefts)):
				for k in range(len(rights)):
					root = TreeNode(i)
					root.left = lefts[j]
					root.right = rights[k]
					trees.append(root)
		return trees
	def get_trees(self, start, end):
		trees = self.get_trees_impl(start, end)
		results = []
		for tree in trees:
			if tree is None:
				results.append([])
			else:
				results.append(tree.to_list(end))
		return results
# %%
s = Solution()
print(s.generateTrees(n=3))
```

## 答案

```python

```

## 选项

### A

```python

```

### B

```python

```

### C

```python

```