[Leetcode] Unique Binary Search Trees

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         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

比较简单的题目，一颗拥有n个节点的树的个数又左右子树的乘积的和来决定，意思就是左子树有0个节点和右子树有n-1个节点的乘积加上左子树有1个和右子树有n-2个的乘积等等等等一直加到左子树有n-1个右子树有0个。在算的过程中可以使用一个HashMap来记录已经求解过的情况来起到加速的效果。

    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    public int numTrees(int n) {
        if(n == 0 || n == 1) return 1;
        else {
            if(map.containsKey(n) == true) return map.get(n);
            else {
                int sum = 0;
                for(int i = 0; i < n; i++) {
                    sum = sum + numTrees(i)*numTrees(n-1-i);
                }
                map.put(n, sum);
                return sum;
            }
        }
    }