题目
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
分析
一看题目，首先是一脸蒙蔽。不知道到底要干嘛！于是百度一波，先了解一下什么事二叉搜索树。
二叉搜索树： 又称二叉查找树，二叉排序树。它可能是一颗空树。它具有的性质：若左子树不空，那么左子树上的所有结点的值都小于它的根结点的值；若右子树不为空，则右子树上所有结点的值均大于它的根结点的值。
那么题目的意图就能理解了。就是从1到n，依次作为根节点生成这样一颗树。
比如第k位作为根节点，那么k左边的数字去生成左子树，k右边的数字去生成右子树。
然后左子树和右子树生成的逻辑也是一样，感觉用递归是最合适的了。
每次递归，都很容易绕晕，感觉是自己的逻辑还不够清晰。
写下这道题的思考路程：
-
先不考虑回归条件，考虑递归逻辑(感觉递归逻辑最难理清楚)。
考虑左子树： 自己刚刚开始想到要让k位左边的数字去生成左子树。那么怎么生成？不考虑细节，应该是让左边的1...k-1数字去生成所有的二叉搜索树数组，那么这个数组里的所有二叉搜索树都可以作为以k为根节点的二叉树的左子树。 考虑右子树： 右子树的生成逻辑和左子树一样。让右边k+1...n的数字去生成所有的二叉搜索树数组，那么这个数组里的所有二叉搜索树都可以作为以k为根节点的二叉树的右子树。
这样的话，递归逻辑代码应该是：
leftTrees = self.p_genrateTrees(1,k-1) #生成所有左子树
rightTrees = self.p_gerateTrees(k+1,n) #生成所有右子树
all_trees = []
for left in leftTrees:
for right in rightTrees:
rootNode = TreeNode(k) #生成根节点
rootNode.left,rootNode.right = left,right #赋值左右子树
all_trees.append(rootNode)
😂感觉要理清递归逻辑，就要先假设自己的函数能够返回正确的东西，不敢思考太深。
比如上面的要生成以k为根节点的所有左子树，就要去生成以1到k-1为根节点所生成的所有二叉搜索树。那么就假设自己的函数可以生成所有的二叉搜索树，先把大体思路先理清楚。
-
考虑回归条件
因为左右子树数组生成的时候，需要左右两个索引参数，由于左参数不能大于右参数，因此回归条件就是 左参数大于右参数。这个时候返回包含一个空对象的数组就可以了。
整体代码如下：
class Solution:
def p_createTree(self,left:int,right:int) -> List[TreeNode]:
if left > right:
return [None]
all_trees = []
for index in range(left,right+1):
leftTrees = self.p_createTree(left,index-1) #拿到所有的左子树
rightTrees = self.p_createTree(index+1,right) #拿到所有的右子树
for le in leftTrees:
for ri in rightTrees:
rootNode = TreeNode(index)
rootNode.left,rootNode.right = le,ri
all_trees.append(rootNode)
return all_trees
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0 :
return []
if n == 1:
return [TreeNode(1)]
else:
return self.p_createTree(1,n)
