目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

示例:

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

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

二、解题思路

递归会超时，可以利用动态规划解决。

dp[0] = 1

dp[1] = 1

dp[2] = dp[0] * dp[1] +

             dp[1] * dp[0]

dp[3] = dp[0] * dp[2] +

             dp[1] * dp[1] + 

             dp[2] * dp[0]

...

dp[n] = dp[0] * dp[n-1] +

             dp[1] * dp[n-2] +

             ... +

             dp[n-2] * dp[1] +

             dp[n-1] * dp[0]

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def numTrees(self, n: int) -> int:
     
    
   

    

     

    
    

     

       dp = [0] * (n + 1)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       dp[0] = 1
     
    
   

    

     

    
    

     

       dp[1] = 1
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for i in range(2, n + 1):
     
    
   

    

     

    
    

     
 for j in range(0, i):
     
    
   

    

     

    
    

     

       dp[i] += dp[j] * dp[i - j - 1]
     
    
   

    

     

    
    

     
 return dp[n]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 # if n == 1 or n == 0:
     
    
   

    

     

    
    

     
 # return 1
     
    
   

    

     

    
    

     
 # res = 0
     
    
   

    

     

    
    

     
 # for i in range(1, n + 1):
     
    
   

    

     

    
    

     
 # res += self.numTrees(i-1) * self.numTrees(n-i)
     
    
   

    

     

    
    

     
 # return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       n = 3
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.numTrees(3)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108716754