Problem: 96. 不同的二叉搜索树

题目描述

思路

一个数字做根节点的话可能的结果为：其左边数字做子树的组合数字乘以其右边数字做子树的个数之积

1.创建备忘录memo；
2.递归分别求取当前数字左边和右边数字做子树的数量（注意下面代码当左边界值大于有边界值时应当反回1）

复杂度

时间复杂度:

$O(n)$；其中$n$是二叉树节点的个数

空间复杂度:

$O(height)$;其中$height$是二叉树的高度

Code

class Solution {
    int[][] memo;

    /**
     * Unique Binary Search Trees
     *
     * @param n Given number
     * @return int
     */
    public int numTrees(int n) {
        memo = new int[n + 1][n + 1];
        return count(1, n);
    }

    /**
     * Unique Binary Search Trees(Implementation function)
     *
     * @param low  Left boundary
     * @param high Right boundary
     * @return int
     */
    private int count(int low, int high) {
        if (low > high) {
            return 1;
        }
        //Check the meme
        if (memo[low][high] != 0) {
            return memo[low][high];
        }
        int res = 0;
        for (int mid = low; mid <= high; ++mid) {
            int left = count(low, mid - 1);
            int right = count(mid + 1, high);
            res += left * right;
        }
        memo[low][high] = res;
        return res;
    }
}