LeetCode 96 不同的二叉搜索树

1 题目描述

给定一个整数n,求以1 … n为节点所组成的二叉搜索树(BST)共有多少种情形?

例子1:

输入:3

输出:5

释义:

对n=3,共有如下5种满足BST的情形:

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

题目出处:LeetCode

2 解决思路

先拿n=3时举个例:

a)root为1时,2、3仅可放在右子树;

b)root为2时,1放左子树,3放右子树;

c)root为3时,1、2仅可放在左子树。

总数为此三种加起来。

至于子树为两个节点的情况,再拿n=2时按上述步骤去处理。

所以可以看到规律,对于n的情形,采用如下步骤计算:

a)root为1时,2…n仅可放在右子树;

b)root为2时,1放左子树,3…n放右子树;

x)root为i时,1…i-1这i-1个节点放左子树,i+1…n这n-i个节点放右子树;

对于上述情况,递归计算即可,最后将各结果加起来,返回条件为n=0或n=1,返回为1。

改进:

上述递归计算时,对用到的子树计算结果有大量重复计算的情形,因递归较深,这样非常耗时。我们可以借助一个map来存储算过的值,这样不同的值仅计算一次。

3 Golang实现代码

https://github.com/olzhy/

var table = make(map[int]int)

func numTrees(n int) int {
    if 0 == n || 1 == n {
        return 1
    }
    if v, ok := table[n]; ok {
        return v
    }
    num := 0
    for i := 1; i <= n; i++ {
        num += numTrees(i-1) * numTrees(n-i)
    }
    table[n] = num
    return num
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝