題目
給定一個(gè)整數(shù) n，生成所有由 1 ... n 為節(jié)點(diǎn)所組成的** 二叉搜索樹 **。
示例：
<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--grey-9-rgb),0.04); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">輸入：3
輸出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解釋：
以上的輸出對(duì)應(yīng)以下 5 種不同結(jié)構(gòu)的二叉搜索樹：
1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3
</pre>
提示：
0 <= n <= 8
思路1
以每一個(gè)i都作一次根節(jié)點(diǎn)，i將數(shù)列分為兩部分，（1，i-1）和（i+1, n)，在前一個(gè)區(qū)間中讓每個(gè)j都做一次根節(jié)點(diǎn)構(gòu)成的樹作為i的左子樹，在后一個(gè)區(qū)間中讓每個(gè)k都做一次根節(jié)點(diǎn)構(gòu)成的樹作為i的右子樹，將所有的情況組合起來(lái)
來(lái)回只用到一個(gè)函數(shù)用來(lái)生成以i為根節(jié)點(diǎn)的樹，遞歸調(diào)用即可，結(jié)束的條件是left > right，返回[None]
# 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]:
if not n:
return []
def new_tree(start, end):
if start > end:
return [None]
all_tree = []
for i in range(start, end+1):
left_tree = new_tree(start, i-1)
right_tree = new_tree(i+1, end)
for left in left_tree:
for right in right_tree:
tree = TreeNode(i)
tree.left = left
tree.right = right
all_tree.append(tree)
return all_tree
return new_tree(1, n)
