LeetCode : 96. Unique Binary Search Trees 二叉搜索树数量

我不是女神ヾ 2021-06-24 16:11 386阅读 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];
        }
    }