欢迎大家来到IT世界,在知识的湖畔探索吧!
本题来自Leetcode，题目传送门：不同的二叉搜索树
难度：中等
编程语言：Go
1. 题目介绍
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。
引用自Leetcode
提示：1 <= n <= 19
2. 解题思路
题干可以提取几个要求：
1. 只有n个节点，且节点值唯一；
2. 每个二叉树是二叉排序数，即左小右大；
3. 每个二叉排序树要用全部的节点点n个。
n个节点，则存在n种root节点的二叉排序树，所以总数 = n * 以i为root节点的二叉树的数量, 转换为几何表达式：
对于f(i),root节点i的左子树有节点(i-1)个，右子树有节点（n-i）个，左右子树又是需要计算可能存在的包含多个节点的二叉树，则：
综合两式，得：
G(n) = G(0) * G(n-1) + G(1)*G(n-2) + … + G(i-1) * G(n-i) + … + G(n-1) * G(0)
3. 源码展示
先写测试
方法实现
Leetcode运算结果
执行用时: 0 ms
内存消耗: 1.8 MB
生活依然要继续，每天拿出半个小时，放下焦虑，用行动来积累更好的自己，我们一起加油！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/89067.html
