子寒的博客
0%

leetcode96 Unique binary search trees 解题报告

发表于

英文原题

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example

1
2
Input: n = 3
Output: 5

分析

     要求的是有多少种可能的情况，可以看作左子树的所有情况数乘以右子树的所有情况数，用递归的话就是numTrees(i-1) * numTrees(n-i)，根节点则是从1到n遍历。同时用一个字典来保存计算过的n值

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numTrees(self, n: int) -> int:
        dic = dict()
        dic[0] = 1
        dic[1] = 1
        def helper(num):
            if num in dic:
                return dic[num]
            
            ans = 0
            
            for i in range(1, num+1):
                ans += helper(i-1) * helper(num - i)
            dic[num] = ans
            return ans
        
        return helper(n)