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)
}

评论

正在加载评论......