跳到主要内容

96. 不同的二叉搜索树[medium]

96. 不同的二叉搜索树[medium]​

https://leetcode-cn.com/problems/unique-binary-search-trees/

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

通过次数46,439 提交次数70,684

Second Try​

2020-07-17

在做0095的时候掉进bug花了大半天，发现后面是0096，顺手再做一遍。

现在在做这题的时候没什么迟疑了，感觉比较顺利成章。甚至脑海里还没仔细思考二叉搜索树要求排列的内在要求，直接把1-n作为顶点来一遍，然后考虑左节点和右节点的笛卡尔积，然后就搞定了。

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        cache = [""] * (n + 1)
        cache[0] = cache[1] = 1

        def combo(n):
            if cache[n] != "":
                return cache[n]
            rv = 0
            for i in range(1, n + 1):
                rv += combo(i - 1) * combo(n - i)
            cache[n] = rv 
            return cache[n]
        return combo(n)
  • 执行用时：20 ms, 在所有 Python 提交中击败了58.00%的用户
  • 内存消耗：12.6 MB, 在所有 Python 提交中击败了33.33%的用户

First Try​

2020-06-09

又是一个典型的套路题，参考答案才理出来的方法，catalan数的数学解法一时半会真是理解不了，只能用程序解法。

  • 考虑n个节点，从左到右作为切分点，在其左右可以分出[0, n-1], [1, n-2]...[n, 0]种可能。
  • 对于每个切分区间，左边作为左子树，右边作为右子树，左右笛卡尔积即可以得到某个切分的所有可能子树。
  • 通过上面的切分，可以把n节点一点点拆分为更小的节点，就实现了通过递归求解的可能。定义0节点和1节点的时候子树形态为1，其他的就可以通过递归计算了。
  • 计算过程中可以把某些计算结果缓存，加快速度。这个缓存数组的存在，该算法就被归纳为动态规划算法，真是廉价的动态规划。
  • 一个困扰了许久的误区，n个节点虽然都有编号，但是谁在左边谁在右边是无所谓的，只有当左右节点树形态不一致的时候才需要计数，编号也只是为了让左右切割的数量不同。考虑节点本身编号的话，直接就绕进了更复杂的区域了。

注意节点编码从1到n，而且存在0区间的情况，因此缓存列表需要为n+1的长度。

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """

        # 重点在于这些节点不需要排序
        cache = [""] * (n + 1)
        cache[0] = cache[1] = 1
        def combine(n):
            if cache[n] != "":
                return cache[n]
            res = 0
            for i in range(1, n + 1):
                res += combine(i - 1) * combine(n - i)
            cache[n] = res
            return res
        return combine(n)
  • 执行用时 :12 ms, 在所有 Python 提交中击败了96.58%的用户
  • 内存消耗 :12.7 MB, 在所有 Python 提交中击败了33.33%的用户
  • 关于catalan数

不懂啊不懂，这个只是在拆分为子树的时候出现了catalan树的递归形态，怎么就能从一开始就识别为catalan数呢？

Catalan Numbers: https://brilliant.org/wiki/catalan-numbers/