前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的95题。
问题描述
给定一个整数 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
分析：
看到这题并没有什么想法，后来是看不同的二叉搜索树 II
func generateTrees(n int) []*TreeNode {
if 0 == n {
return nil//没有这个分支判断，n为0时leetcode会认为返回是[[]],而他期待的结果是[]
}
return nTree(1, n)
}
func nTree(begin, end int) []*TreeNode {
ret := make([]*TreeNode, 0)
if begin > end {
ret = append(ret, nil)
return ret
}
for i := begin; i <= end; i++ {
lefts := nTree(begin, i-1)
rights := nTree(i+1, end)
for _, l := range lefts {
for _, r := range rights {
root := &TreeNode{i, l, r}
ret = append(ret, root)
}
}
}
return ret
}
通过循环历遍每一个元素。以这个元素作为根节点，那么比它小的元素就只能是属于它的左子树，比它大的节点属于它的右子树。 那么剩下的问题，就是求左子树的所有可能的集合，和右子树的所有可能的集合。这两个问题和原问题本质上是一样求法。这样问题就被划分为了两个子问题。最后再将两边所有可能的组合都合起来，构成一棵树。 每当确定了一个根节点（最外层循环），之后的问题就是一个动态规划的问题。将所有可能的左子树的组合存在lefts中，右子树的可能组合放在rights中。最后再组合。
若在begin > end分支中直接返回nil，这需要在最内层循环中判断，像这样
总结：
勤思考。
结语
不管怎么样好好加油。
