LeetCode 95 不同的二叉搜索树 II

1 题目描述

给定一个整数n，生成节点为1…n的所有的二叉搜索树（BST）。

例子1：

输入：3

输出：

[[1,null,3,2],[3,2,null,1],[3,1,null,null,2],[2,1,3],[1,null,2,null,3]]

释义：

如上输出为对应n为的5的所有的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

题目出处：LeetCode

2 解决思路

写一个generate函数，其负责生成包含begin…end节点的BST。

初始时，begin为1，end为n。

欲求所有的BST，可以按如下步骤来计算：

a）当root为begin时，root的左子树为空，右子树为包含begin+1…end的BST；

b）当root为begin+1时，root的左子树为begin，右子树为包含begin+2…end的BST；

…

x）当root为i时，root的左子树为包含begin…i-1的BST，右子树为包含i+1…end的BST；

…

递归调用如上步骤，直至begin大于end，则返回空树数组，或者begin=end，返回仅包含begin一个根节点树的数组。

3 Golang实现代码

https://github.com/leileiluoluo/

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func generate(begin, end int) []*TreeNode {
    if begin > end {
        return []*TreeNode{nil}
    }
    if begin == end {
        return []*TreeNode{{Val: begin}}
    }
    var trees []*TreeNode
    for i := begin; i <= end; i++ {
        left := generate(begin, i-1)
        right := generate(i+1, end)
        for _, j := range left {
            for _, k := range right {
                root := &TreeNode{Val: i, Left: j, Right: k}
                trees = append(trees, root)
            }
        }
    }
    return trees
}

func generateTrees(n int) []*TreeNode {
    if 0 == n {
        return []*TreeNode{}
    }
    return generate(1, n)
}

LeetCode 95 不同的二叉搜索树 II

相关文章

评论