96_不同的二叉搜索树

类型：树

• 96. 不同的二叉搜索树 💛

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

  ❓ 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

  💡 动态规划

  假设我们要计算 numTrees(5) 那么，

  numTrees(5) = 
  	numTress(0) * numTress(4)
  + numTress(1) * numTress(3)
  + numTress(2) * numTress(2)
  + numTrees(3) * numTrees(1)
  + numTrees(4) + numTrees(0)

  而边界条件，

  numTress(0) = 1
  numTress(1) = 1
  numTress(2) = 2
  numTress(3) = numTress(0) * numTress(2) 
  						 + numTress(1) * numTress(1)
  						 + numTrees(2) * numTress(0)
  ...

  代码如下：

  class Solution:
      def numTrees(self, n: int) -> int:
          counts = [1, 1, 2]
          if n <= 2:
              return counts[n]
          for k in range(3, n + 1):
              count = 0
              for i in range(k):
                  count += counts[i] * counts[k - i - 1]
              counts.append(count)
          return counts[-1]

  时间复杂度：O(n^2)，空间复杂度：O(n)