题目

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.

思路

给定n，求不重复二叉查找树的数量，可以分为n种情况，根节点是x（x的取值从1到n），左边都是比x小的数，右边都是比x大的数。左右两边又可以递归遍历根节点，求出在根节点为该数的情况下的不重复二叉查找树的数量，当左边的不重复二叉查找树的数量为y，右边为z时，该根节点为该数的不重复二叉查找树的数量为y*z。

代码

class Solution { public: int numTrees(int n) { vector<int> data(n+1); data[0] = 1; data[1] = 1; helper(data, n); return data[n]; } void helper(vector<int>& data, int n) { int count = 0; for (int i = 0; i <= n - 1; i++) { if (data[max(n - 1, i)] == 0) { helper(data, max(n - 1 - i, i)); } count += data[i] * data[(n - 1 - i)]; } data[n] = count; } };