不同的二叉搜索树

095_generate_BST & 096_count_BST

95.给定一个整数 n,生成所有由 1 … n 为节点所组成的二叉搜索树。

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

示例:

输入: 3

95.输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]

96.输出: 5

解释:

以上的输出对应以下 5 种不同结构的二叉搜索树:

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

我感觉之前的学习曲线有点太平坦了,为了适当增大学习曲线斜率,我把Leetcode日志模板生成器升级了,从现在开始,题号不会顺序增减,而是随机产生一个题号,同时产成特定题号的概率与题号大小成线性负相关.这样感觉好玩点.

第一个幸运儿是95,看了一眼题决定把它和96一起解决.

这两道题都是BST,先找有多少种可能,再把它们生成出来.

先来解决数数的问题.

1. 动态规划(96)

动态规划的关键在于分对子问题,所谓divide.

首先申明两个状态:

  • A(n) 表示 以1~n为节点组成的BST种数
  • B(i,n)表示 根节点为i时,以1~n为节点组成的BST种数

那么有:

  • A(n) =

  • B(i,n) = A(i-1) * A(n-i)

这分别是由于:

  • 计算A(n),只需限制根节点为(1~n),则可分为n个子问题,即转化为求B
  • 计算B(i,n),只需分开考虑左子树,和右子树.即转化为求A

问题就解决了

为了方便理解,求解流程是: A(1) -> B(1,2)&B(2,2) -> A(2) -> B(1,3)&B(2,3)&B(3,3) -> A(3) -> ……

class Solution:
    def numTrees(self, n: int) -> int:
      a = [0]*(n+1) # a[i] = A(i)
      a[0] = a[1] = 1
      temp =0
      for i in range(2,n+1):
        for j in range(1,i+1):
          temp += a[j-1]*a[i-j]
        a[i],temp = temp,0
      return a[n]

执行用时: 52 ms, 在Unique Binary Search Trees的Python3提交中击败了13.54% 的用户

内存消耗: 13.3 MB, 在Unique Binary Search Trees的Python3提交中击败了0.00% 的用户


2.打表(96)

你也看到了,方法一的效果不太好,这些人是怎么把时间,内存刷上去的?

我决定打表试下,先用自己电脑跑一遍表:

class Solution:
    def numTrees(self, n: int) -> int:
        a = [0] * (n + 1)  # a[i] = A(i)
        a[0] = a[1] = 1
        temp = 0
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                temp += a[j - 1] * a[i - j]
            a[i], temp = temp, 0
        return a[n]


if __name__ == '__main__':
    code = '''
    class Solution(object):
        def numTrees(self, n):
            result = {}
            return result[n]
    '''

    result = [0, 1]
    for i in range(2, 20):
        result.append(Solution().numTrees(i))
    print(code.format(str(result)))

然后把下面这段代码丢进去跑,结果发现时间内存不变.

是平台崩了?

还是我没充钱?

class Solution(object):
    def numTrees(self, n):
        result = [0, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190]
        return result[n]

执行用时: 80 ms, 在Unique Binary Search Trees的Python3提交中击败了2.59% 的用户

内存消耗: 13.2 MB, 在Unique Binary Search Trees的Python3提交中击败了0.00% 的用户


3. 动态规划->递归(95)

不管了,反正这道题我会了,平台怎么弄出来的鬼成绩我也是彻底想不明白了,继续做下一道

95和96差不多,不同的是需要把结构也保存下来,

按照原来的思路,引入一个tree_list拿来存结构,直接写,发现其实贼麻烦,不要相信”看懂96就行,95写起来很简单”

想了很久,发现只有递归大法好,思路是一样的,只不过是用递归来写而已,在这个方法之后我将补上一个96-递归的代码

我是先看了这里的代码再来写的,结果无论怎么写都和原来的一样,就像是直接copy的…

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
      if n == 0: return []
      return self.generateTreesR(1, n)

    def generateTreesR(self, left, right):
      if left > right:return [None]
      result = []
      for i in range(left, right + 1):
          left_nodes = self.generateTreesR(left, i - 1)
          right_nodes = self.generateTreesR(i + 1, right)
          for left_node in left_nodes:
              for right_node in right_nodes:
                  root = TreeNode(i)
                  root.left = left_node
                  root.right = right_node
                  result.append(root)
      return result

执行用时: 84 ms, 在Unique Binary Search Trees II的Python3提交中击败了58.08% 的用户

内存消耗: 15 MB, 在Unique Binary Search Trees II的Python3提交中击败了0.00% 的用户

4. 直接递归(96)

现在需要构造一个递归函数,它能计算出(left,right)之间的所有节点的BST种数,

class Solution:
    def numTrees(self, n: int) -> int:
      if n == 0: return 0
      return self.numTreesR(1,n)

    def numTreesR(self,left,right):
      result = 0
      if left > right:return 1
      if left == right:return 1
      for i in range(left, right + 1):
          left_num = self.numTreesR(left, i - 1)
          right_num = self.numTreesR(i + 1, right)
          result += right_num*left_num
      return result

答案正确,但时间超标了,未通过

5. 带备忘录的递归(96)

既然直接递归通不过,那就是时候召唤字典了

class Solution:
    def __init__(self):
      self.dic = {}

    def numTrees(self, n: int) -> int:
      if n == 0: return 0
      return self.numTreesR(1,n)

    def numTreesR(self,left,right):
      result = 0
      if left > right:return 1
      if left == right:return 1
      if str(left)+","+str(right) in self.dic.keys():
        return self.dic[str(left)+","+str(right)]
      for i in range(left, right + 1):
          left_num = self.numTreesR(left, i - 1)
          right_num = self.numTreesR(i + 1, right)
          result += right_num*left_num
      self.dic[str(left)+","+str(right)] =result
      return result

执行用时: 64 ms, 在Unique Binary Search Trees的Python3提交中击败了5.19% 的用户

内存消耗: 13.1 MB, 在Unique Binary Search Trees的Python3提交中击败了0.00% 的用户

本文总字数: 3465