专栏首页Petrichor的专栏leetcode: 96. Unique Binary Search Trees

leetcode: 96. Unique Binary Search Trees

Problem

# Given n, how many structurally unique BST's (binary search trees) 
# that store values 1...n?
#
# For example,
# Given n = 3, there are a total of 5 unique BST's.
#
#   1         3     3      2      1
#    \       /     /      / \     \
#    3     2      1      1  3     2
#   /     /       \                \
#  2     1         2               3

Idea

二叉查找树可以任意取根,只要满足中序遍历有序的要求就可以。

选取一个结点为根,就把结点切成左右子树,以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积,
所以总的数量是将以所有结点为根的可行结果累加起来。

记得考虑 子树 为 空树 的情况。

AC

DFS (但是会Time Limit Exceeded):

class Solution():
    def numTrees(self, n):
        if n <= 1:
            return 1
        res = 0
        for i in range(0, n):   # 左子树的node数 有 0~n-1种可能
            res += self.numTrees(i) * self.numTrees(n-i-1)
        return res

DP:

# Time:  O(n^2)
# Space: O(n)
class Solution():
    def numTrees(self, n):
        res = [1, 1]
        for i in range(2, n+1):
            tmp = 0
            for j in range(0, i):    # 左子树的node数 有 0~n-1种可能
                tmp += res[j] * res[i-j-1]
            res.append(tmp)
        return res[-1]


if __name__ == "__main__":
    assert Solution().numTrees(3) == 5

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 39. Combination Sum

    JNingWei
  • leetcode: 40. Combination Sum II

    JNingWei
  • 【leetcode】背包问题

    完全背包的特点恰是每种物品可选无限件,所以就可以并且必须采用 w = W[i]…carry 的顺序循环:

    JNingWei
  • 《了不起的 nodejs》中 TwitterWeb 案例 bug 解决

    了不起的nodejs算是一本不错的入门书,不过书中个别案例存在bug,按照书中源码无法做出和书中相同效果,原本兴奋的心情掺杂着些许失落。 现在我们看一下第七章H...

    叙帝利
  • 微信小程序开发(二)图片上传+服务端接收

    这里的filePath就是图片的存储路径,类型居然是个String,也就是 只能每次传一张图片,我以前的接口都是接收一个array,我本人又是一个半吊子的php...

    开发者技术前线
  • 高精度运算

    在写Java代码时候,我们其实很少去考虑高精度运算,即使遇到无法避免高精度的计算问题也不会太烦恼,因为有大整数类BigInteger以及BigDecimal工具...

    每天学Java
  • python中全局变量、局部变量、类变量、实例变量简析

    因为python为动态语言,处理变量的方式与一些静态语言(比如C++)不大一样,在这里对这些变量进行小小的总结

    用户7886150
  • 前缀树问题-LeetCode 409、412、414、415、419、421

    给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:...

    算法工程师之路
  • rabbitmq搭建集群踩坑记

    三台节点启动之后,想要使用s146作为集群主节点,在s151上将该节点加入s146集群时,报如下错误。

    我是李超人
  • MIT通用人工智能课视频放出,要教你用工程方法构建人类智能

    李林 发自 凹非寺 量子位 出品 | 公众号 QbitAI ? MIT最近开了一门“通用人工智能(AGI)”课,要带着学生们用工程方法来探索构建人类级智能的研究...

    量子位

扫码关注云+社区

领取腾讯云代金券