96. Unique Binary Search Trees

题目描述和难度

• 题目描述：

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

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

• 题目难度：中等。
• 英文网址：96. Unique Binary Search Trees 。
• 中文网址：96. 不同的二叉搜索树 。

思路分析

求解关键：

参考解答

参考解答1

public class Solution2 {

    // 递归方法实现：这里一定要用上记忆化搜索
    // 因为有大量重复子问题

    // base case 是，当 n = 0 或者 n = 1 时，显然 BST 数量只能有 1 个。

    // 一定要加上缓存
    private int[] memo;

    public int numTrees(int n) {
        if (n < 0) {
            return 0;
        }
        if (n < 2) {
            return 1;
        }
        memo = new int[n + 1];
        memo[0] = 1;
        memo[1] = 1;
        return helper(n);
    }

    private int helper(int n) {
        if (memo[n] != 0) {
            return memo[n];
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += helper(i - 1) * helper(n - i);
        }
        memo[n] = sum;
        return sum;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int n = 3;
        int numTrees = solution2.numTrees(n);
        System.out.println(numTrees);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0096-unique-binary-search-trees ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。