二叉查找树和二叉搜索树_什么是满二叉树

2024年 7月 26日下午2:08 • 激活谷笔记

动态规划——不同的二叉搜索树　　注：本系列仅作为学习记录，有问题请友善私聊。

　　96. 不同的二叉搜索树 – 力扣（LeetCode） (leetcode-cn.com)

　　这个题首先得知道啥叫二叉搜索树，前面已经学过了，这里就不再说了。龙雨城：leetcode系列——验证二叉搜索树　　这个题最好手动比划比划，其实就是分别以1到n的数为根节点，这样分类的话就不会错。

　　还是看五步骤吧：　　第一步：dp[i]应该表示1到i为节点组成的搜索二叉树的个数为dp[i] 　　第二步：递推公式：看上面的图，分别以1到i为根节点，分为两个分支，每个分支的数量m就能组成dp[m]个树。　　比如i=3，

来源：代码随想录　　所以递推公式为：

　　第三步：初始化，这里dp[0]和dp[1]应该都为1，dp[0]不能为0，否则乘积都是0了。　　第四步：遍历顺序：上面的图已经说明了。　　第五步：手动推导，这里其实很容易漏画，所以还是在官网测试吧。

　　这道题难在递推公式，这么想吧：2和3构成的树，与1和2构成的树结构上没有任何区别。所以才有：

　　更新：C++版本　　这里其实与节点的值无关，与节点两边的子节点数量有关：　　比如n=3，那么1、2、3或者是3、6、9能构成的BST的总数是一样的，只是节点上的值不一样罢了，所以，这里的n的实际意义是n个节点，且n个节点值肯定是不一样的，也就是会形成有序的一个序列，自然就能够形成BST。　　那么，根节点需要一个，所有的子节点就需要n-1个，而子节点分为左子树和右子树，意思是左右子树的节点数目加起来共n-1个。　　如果左子树分了left个节点，右子树自然只能有n-1-left个节点。　　这时可以把左右子树再单独看成一个根节点，各自节点总数分别是left和n-1-left，再重复上述的步骤，这样就转化为无数个子问题的幂解。　　这里求解能够有多少种方式呢？实际上需要我们从i=1个节点开始，看i个节点能够有多少种可能，最后i=n。　　比如n=3，根节点占一个，还剩两个可用，那么有三种情况：左边2个，右边0个左边1个，右边1个左边0个，右边2个　　这三种构成的树一定是不一样的，如何用等式表示呢：　　
　　这里是三部分累加，分别对应上面三种情况，那如果n=4，则需要累加4次，因为某一边的个数可以从0-3个。　　比如以某个节点为root，包含root总共有n个节点可拿来构造树，某一边有 for i in [0, n-1]个节点，那么另一边则是[n-1-i]个节点，此时：　　
$dp[n]=\sum_{i=1}^{n-1}{dp[i]*dp[n-1-i]}$ 　　关键点来了，这里的root是不是也可以是某个树的一个子节点呢？　　如果这样的话，我们假设总共用m个节点来构造BST，上面的root只是这m中的一个，那么是不是应该有：设拿m个节点构造BST共有total种
$total=\sum_{n=1}^{m}{dp[n]*dp[m-1-n]}$ 　　所以这里是两层for循环，内层对应的是n，外层对应的是m。　　如有理解不当，敬请指出。

二叉查找树和二叉搜索树_什么是满二叉树

相关推荐