1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| // @Title: 不同的二叉搜索树 II (Unique Binary Search Trees II)
// @Author: 15816537946@163.com
// @Date: 2019-11-18 20:58:51
// @Runtime: 4 ms
// @Memory: 5.5 MB
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
var res []*TreeNode
if n <= 0 {
return res
}
// 所有符合条件的inorder是一样的
in := make([]int, n)
for i := range in {
in[i] = i + 1
}
// 利用inorder生成所有可能的preorder
pres := getPres(in)
// 利用preorder和inorder生成 二叉树
for _, pre := range pres {
temp := preIn2Tree(pre, in)
res = append(res, temp)
}
return res
}
func getPres(in []int) [][]int {
size := len(in)
if size <= 1 {
return [][]int{in}
}
if size == 2 {
return [][]int{
[]int{in[1], in[0]},
[]int{in[0], in[1]},
}
}
res := [][]int{}
for i := 0; i < size; i++ {
// 以in[i]为root
// 获取in[i]左侧的preorder
ls := getPres(in[:i])
// 获取in[i]右侧的preorder
rs := getPres(in[i+1:])
for _, l := range ls {
for _, r := range rs {
temp := make([]int, 1, size)
// in[i]为root, 所以,应该为0位
temp[0] = in[i]
temp = append(temp, l...)
temp = append(temp, r...)
// 汇总结果
res = append(res, temp)
}
}
}
return res
}
func preIn2Tree(pre, in []int) *TreeNode {
if len(in) == 0 {
return nil
}
res := &TreeNode{
Val: pre[0],
}
if len(in) == 1 {
return res
}
idx := indexOf(res.Val, in)
res.Left = preIn2Tree(pre[1:idx+1], in[:idx])
res.Right = preIn2Tree(pre[idx+1:], in[idx+1:])
return res
}
func indexOf(val int, nums []int) int {
for i, v := range nums {
if v == val {
return i
}
}
return -1
}
|