Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

    Example:

    1. Input: 3
    2. Output: 5
    3. Explanation:
    4. Given n = 3, there are a total of 5 unique BST's:
    6.    1         3     3      2      1
    7.     \       /     /      / \      \
    8.      3     2     1      1   3      2
    9.     /     /       \                 \
    10.    2     1         2                 3

    题意

    给定n个整数1，2，…，n，用这些整数构成二叉搜索树的结点。求共可以形成多少符合规范的二叉搜索树。

    思路

    实际上有点类似于排列组合。如果两棵树的结点数相同，但它们的根节点不同，那么这两颗树一定不同；而当根结点相同时，只要左右子树结构不同，那么这两棵树还是不同的。所以对于n个整数，我们每次选取一个整数作为根结点，统计所有不同左右子树的组合数，得到的就是以该整数为根结点构成的不同树的数量，再变换根结点累加所有这样的值，得到的就是最终答案。

    假设n个整数构成的不同的BST的数目为T(n)，而在n个整数中选取一个 i 作为根结点得到的不同的BST的数目为t(n, i)，则可以得到：

    image.png

    普遍情况可以得到如下公式：

    96. Unique Binary Search Trees (M) - 图2

    代码实现 - 递归

    1. class Solution {
    2.     Map<Integer, Integer> record = new HashMap<>();
    4.     public int numTrees(int n) {
    5.         if (n == 0 || n == 1) {
    6.             return 1;
    7.         }
    9.         int count = 0;
    10.         if (record.containsKey(n)) {
    11.             count =  record.get(n);
    12.         } else {
    13.             for (int i = 1; i <= n; i++) {
    14.                 count += numTrees(i - 1) * numTrees(n - i);
    15.             }
    16.             record.put(n, count);
    17.         }
    19.         return count;
    20.     }
    21. }

    代码实现 - 迭代

    1. class Solution {
    2.     public int numTrees(int n) {
    3.         if (n == 0 || n == 1) {
    4.             return 1;
    5.         }
    7.         int[] record = new int[n + 1];
    8.         record[0] = 1;
    9.         record[1] = 1;
    10.         for (int i = 2; i <= n; i++) {
    11.             for (int j = 1; j <= i; j++) {
    12.                 record[i] += record[j - 1] * record[i - j];
    13.             }
    14.         }
    16.         return record[n];
    17.     }
    18. }