分治的思想为将大问题分解为子问题，子问题再分解为更小的子问题，直到不能再拆分，然后再合并子问题的结果，通常需要用到递归。关键是要找对如何拆解问题。
5.1 不同的二叉搜索树
问题描述：给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。
思路：根据二叉搜索树的特点，左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点，同时对于每一个子树也要满足以上条件。1…n有序序列，假设对于每一个值i作为根节点，可以先求的[1，i - 1]构成的二叉搜索左子树，[i + 1, n]构成的二叉搜索右子树，然后从左右子树中各选一个作为当前根节点的左右子树。
示例代码：
func generateTrees(n int) []*TreeNode {
return _generateTrees(1, n)
}
func _generateTrees(start, end int) []*TreeNode {
if start > end {
return []*TreeNode{nil}
}
res := []*TreeNode{}
for i := start; i <= end; i++ {
left := _generateTrees(start, i - 1)
right := _generateTrees(i + 1, end)
for _, l := range left {
for _, r := range right {
tmp := &TreeNode{
Val: i,
Left: l,
Right: r,
}
res = append(res, tmp)
}
}
}
return res
}
5.2 为运算表达式设计优先级
题目描述：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
思路：对于每个预算式形如x op y，其左右表达式也可以看做一个形如x op y的运算式，对左右两边的运算式的所有结果进行计算，就可以得到最终的结果。
示例代码：
func diffWaysToCompute(expression string) []int {
num, err := strconv.Atoi(expression)
// 如果为纯数字，直接返回数字
if err == nil {
return []int{num}
}
res := []int{}
for i, ch := range expression {
// 跳过非运算符
if ch != '+' && ch != '-' && ch != '*' {
continue
}
// 计算运算符左右两边子表达式的结果
left := diffWaysToCompute(expression[ : i])
right := diffWaysToCompute(expression[i + 1 : ])
for _, l := range left {
for _, r := range right {
var tmp int
switch ch {
case '+': tmp = l + r
case '-': tmp = l - r
case '*': tmp = l * r
}
res = append(res, tmp)
}
}
}
return res
}