本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

不同的二叉搜索树

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

二、思路分析

• 本题依旧是动态规划。初看此题时容易被题目吸引注意力误认为是二叉树考点。实际上只是借助了二叉树的外壳内在是动态规划。

为什么是动态规划

• 为什么我说考察的是动态规划呢？因为题目中并没有要求我们对二叉树进行遍历修改或者使用到二叉树的特性。题目中仅仅是使用了二叉树是两个分支的特性
• 我们将题目可以做如下的理解。在N 个节点摆出二叉树求有多少种摆法 。
• 二叉树只会有两颗树枝。当我们知道N-1个节点构成二叉树的个数时，N个节点就是在N-1的二倍基础上进行平衡等操作。所以N和N-1是有关联的
• 所以笔者才说这里是动态规划的考点

正式分析

• 既然是动态规划，那么我们还是原来的三板斧。转换方程–》初始值–》计算

转换方程

• 二叉树是左右两颗子树，所以我们设当前节点个数为m 。那么m-1个节点组成的二叉树个数则为F(m-1) 。 而由m-1个节点组成的二叉树可以在第m个节点的左边，也可以在他的右边。

• 所以F(m)至少包含2*F(m-1)。 但是m以下的节点数不仅仅只有m-1 。 还有m-2 。
• 此时我们将m-1进行分堆，比如分成k 和m-1-k 两堆 。 而分别有k个节点可以组成二叉树的可能我们叫做F(k) ,由(m-1-k)组成的二叉树可能我们叫做F(m-1-k)。
• 而k和m-1-k两堆分别对应m节点作为他的左子树和右子树 。 这里有的人可能认为左右可以对调应该是两倍。这里我们的k是从1到m-2的。所以这里不需要两倍

• 加入我们m节点是5 。那么我们的m=5节点左子树会出现如下情况 F(1),F(2),F(3) ，而右子树分别对应的是F(3),F(2),F(1) 。

• 所以F(m)除了包含2*F(m-1)外，还有F(k)*F(m-1-k)所有的和。这里的k范围1<=k<=m-1-1。

• 最终我们可以确定如下转换方程式