• Posted by 微博@Yangsc_o
• 原創文章，版權宣告：自由轉載-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0

95. 不同的二元搜尋樹 II

給你一個整數 n ，請你生成並返回所有由 n 個節點組成且節點值從 1 到 n 互不相同的不同 二元搜尋樹 。可以按 任意順序 返回答案。

範例 1：

輸入：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

解析：
先看如何構造一顆平衡二元搜尋樹

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
}

根據題目的意思，需要在上面的程式碼中，在選擇根結點的時候，遍歷跟節點所有的可能；
即：i := (start + end) / 2 的可能值為從start到end

	for  i := start; i <= end; i++{
		root := &TreeNode{Val: i};
	}

當找到root節點時，問題就變為如何構建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 節點的所有可能
    for i:= start; i <= end;i ++ {
        left := helper(start,i - 1)
        right := helper(i + 1 ,end)
        // 2.遞迴所有 root 節點的左右子樹
        for _, leftNode := range left {
            for _, rightNode := range right {
                 // 3.給 root 節點窮舉所有左右子樹的組合
                root := &TreeNode{Val: i}
                root.Left = leftNode
                root.Right = rightNode
                res = append(res, root)
            }
        }
    }
    return res
}

參考

Krains's Blog-不同的二元搜尋樹 II

你的鼓勵也是我創作的動力

打賞地址