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
}