- Posted by 微博@Yangsc_o
- 原創(chuàng)文章霜威，版權(quán)聲明：自由轉(zhuǎn)載-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0
95. 不同的二叉搜索樹 II
給你一個(gè)整數(shù) n 俏拱，請(qǐng)你生成并返回所有由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的不同 二叉搜索樹 语淘÷獍可以按 任意順序 返回答案病毡。
示例 1：
image.png
輸入：n = 3
輸出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：
輸入：n = 1
輸出：[[1]]
提示：
1 <= n <= 8
解析：
先看如何構(gòu)造一顆平衡二叉搜索樹
func generateTrees(n int) *TreeNode {
return helper(1, n)
}
func helper(start, end int) *TreeNode {
if start > end {
return nil
}
// 平衡二叉搜索樹
i := (start + end) / 2
root := &TreeNode{Val: i}
root.Left = helper(start, i-1)
root.Right = helper(i+1, end)
return root
}
根據(jù)題目的意思克胳，需要在上面的代碼中，在選擇根結(jié)點(diǎn)的時(shí)候臼勉，遍歷跟節(jié)點(diǎn)所有的可能；
即：i := (start + end) / 2 的可能值為從start到end
for i := start; i <= end; i++{
root := &TreeNode{Val: i};
}
當(dāng)找到root節(jié)點(diǎn)時(shí)餐弱，問題就變?yōu)槿绾螛?gòu)建root的左右子樹宴霸。
固定左孩子，遍歷右孩子
for _, leftNode := range left {
for _, rightNode := range right {
root := &TreeNode{Val: i}
root.Left = leftNode
root.Right = rightNode
}
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
return helper(1,n)
}
func helper(start,end int) []*TreeNode {
res := make([]*TreeNode, 0)
if start > end {
res = append(res, nil)
return res
}
// 1.窮舉所有以 i 為 root 節(jié)點(diǎn)的所有可能
for i:= start; i <= end;i ++ {
left := helper(start,i - 1)
right := helper(i + 1 ,end)
// 2.遞歸所有 root 節(jié)點(diǎn)的左右子樹
for _, leftNode := range left {
for _, rightNode := range right {
// 3.給 root 節(jié)點(diǎn)窮舉所有左右子樹的組合
root := &TreeNode{Val: i}
root.Left = leftNode
root.Right = rightNode
res = append(res, root)
}
}
}
return res
}
