LeetCode96. 不同的二叉搜索树

$\color{DodgerBlue}{1.题目描述}$

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

难度：中等

示例 1：

输入： n = 3
输出： 5
复制代码

示例 2：

输入： n = 1
输出： 1
复制代码

$\color{DodgerBlue}{2.解题思路}$

1. $1-n$ 的整数，每一个整数都可以作为一个根节点，然后左右两个子树又可以作为二叉搜索树的情况
2. 于是可以利用动态规划来，将问题逐步分解下去
3. 假设$G(n)$表示我们要求的$1-n$ 的互不相同的二叉搜索树的种树 $F(i)$为节点i作为根节点的二叉搜索树的种树，则 $G(n) = F(1)+F(2)+…+F(i)…+F(n)$