Tree - 95. Unique Binary Search Trees II
95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路:
与96题相比,这题要求输出所有的bst,采用递归求解的办法,对于一个节点递归求解左边的bst和右边的bst,再组合起来。
代码:
go:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
if n == 0 {return nil}
return genTree(1, n)
}
func genTree(start, end int) []*TreeNode {
var list []*TreeNode
if (start > end) {
list = append(list, nil)
return list
}
for i := start; i <= end; i++ {
left := genTree(start, i - 1);
right := genTree(i + 1,end);
for _, lnode := range left {
for _, rnode := range right {
list = append(list, &TreeNode{
Val: i,
Left : lnode,
Right: rnode,
})
}
}
}
return list
}