• 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 

解析：
先看如何构造一颗平衡二叉搜索树

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 

当找到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 

参考

Krains's Blog-不同的二叉搜索树 II

你的鼓励也是我创作的动力

打赏地址