LeetCode : 96. Unique Binary Search Trees 二叉搜索树数量 我不是女神ヾ 2021-06-24 16:11 289阅读 0赞 **试题** Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST’s: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 **代码** 这一题首先的想法是,以1-n中所有的数作为根节点。因为根节点不同所以可以对数量求和。 当以m为根节点,那么小于m的一定在左子树,大于m的一定在右子树。这样的话我们可以用左子树的方案数\*右子树方案数来获得以m为根节点的方案数量。而左子树或右子树的方案数问题又回归到了原问题。另外一个注意点是无需考虑节点数值大小,而只需考虑个数。也就是代码中n-i。 为了降低重复计算,可以使用数组存储。 递归原版: class Solution { public int numTrees(int n) { if(n==0) return 1; int tmp = 0; for(int i=1; i<=n; i++){ tmp += numTrees(i-1) * numTrees(n-i); } return tmp; } } 超时优化: class Solution { public int numTrees(int n) { int[] mem = new int[n+1]; mem[0] = 1; return numTrees(n, mem); } private int numTrees(int n, int[] mem){ if(mem[n]!=0) return mem[n]; for(int i=1; i<=n; i++){ mem[n] += numTrees(i-1, mem) * numTrees(n-i,mem); } return mem[n]; } }
还没有评论,来说两句吧...