Category Archives: Tree

Unique Binary Search Trees leetcode

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n? For example, Given n = 3, there are a total of 5 unique BST’s. 这道题目,乍一看很吓人,其实仔细分析,有如下规律:当我们在1-n中选择i作为根,其可能出现的情况为[1,i-1]中BST种类 和 [i+1,n]中BST种类的 乘积, 因此n个节点的总可能性就是把1到n逐步作为根节点的情况总数,而每一个情况又可以按照同样的方式继续计算,因此,我们可以将问题逐步缩小。tip:可以用DP讲计算过的结果存储起来。

Posted in 算法题, Tree | Leave a comment