96. 不同的二叉搜索树

题目： 给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

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

题目来源：力扣（LeetCode） https://leetcode-cn.com/problems/unique-binary-search-trees/

解题思路：

首先必须了解什么叫二叉搜索树： 二叉搜索树（Binary Search Tree）（又称二叉查找树或二叉排序树）。

它可以是一棵空树，或者是具有下列性质的二叉树：

1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3、左、右子树也分别为二叉排序树。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势。

---

对于有 n 个节点，这 n 个节点可以分别作为二叉搜索树的树根，假设 n 个节点构成的二叉搜索树为G(n)，从这 n 个节点中选一个节点 i 作为树根，能构成的二叉搜索树设为 f(i,n)，f(i,n)=G(i-1)*G(n-i)，即左右子树都为二叉搜索树的所有可能数。

G(n) = f(1,n)+f(2,n)+…+f(n,n)。

对于 n 个节点可构成的二叉搜索树的数目只与节点的个数有关。不同节点作为根节点的二叉搜索树是不同的。将 n 个节点的原问题划分为 n 个 n-1 个节点的子问题（一直划分下去），n 个节点中的每个节点作为当前阶段的状态变量的一种取值，只要当前节点一确定，下一阶段的结果与当前阶段之前的状态变量无关，满足无后效应。

在这里每个阶段的子问题或者不同阶段的子问题可能是重复的，若采用递归的方法求解子问题，则会重复计算这些子问题，增加计算复杂度。所以这里采用递归，保存每一个不同子问题的解到表中，当碰到相同子问题时，只需要从表中取即可。

代码：

public static int numTrees(int n) { List<Integer> array = new ArrayList<>(); int temStor = 0; array.add(1); array.add(1); for (int i = 2; i <= n; i++) { if (i%2==0){ for (int j = 0; j < i/2; j++) { temStor += array.get(j)*array.get(i-1-j); } array.add(temStor*2); } if (i%2==1){ for (int j = 0; j < i/2; j++) { temStor += array.get(j)*array.get(i-1-j); } array.add(temStor*2+array.get(i/2)*array.get(i/2)); } temStor = 0; } return array.get(n); }

方法二：数学演绎法

参考leetcode

上述递推关系式是可以求出来的，即 卡塔兰数

欢迎大家一起交流。