原题链接:http://oj.leetcode.com/problems/unique-binary-search-trees/这道题要求可行的二叉查找树的数量,其实二叉查找树可以任意取根,只要满足中序遍历有序的要求就可以。从处理子问题的角度来看,选取一个结点为根,就把结点切成左右子树,以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积,所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下:
熟悉
卡特兰数的朋友可能已经发现了,这正是
卡特兰数的一种定义方式,是一个典型的动态规划的定义方式(根据其实条件和递推式求解结果)。所以思路也很明确了,维护量res[i]表示含有i个结点的二叉查找树的数量。根据上述递推式依次求出1到n的的结果即可。
时间上每次求解i个结点的二叉查找树数量的需要一个i步的循环,总体要求n次,所以总时间复杂度是O(1+2+...+n)=O(n^2)。空间上需要一个数组来维护,并且需要前i个的所有信息,所以是O(n)。代码如下:
public int numTrees(int n) {
if(n<=0)
return 0;
int[] res = new int[n+1];
res[0] = 1;
res[1] = 1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<i;j++)
{
res[i] += res[j]*res[i-j-1];
}
}
return res[n];
}
这种求数量的题目一般都容易想到用动态规划的解法,这道题的模型正好是卡特兰数的定义。当然这道题还可以用卡特兰数的通项公式来求解,这样时间复杂度就可以降低到O(n)。因为比较直接,这里就不列举代码了。如果是求解所有满足要求的二叉树(而不仅仅是数量)那么时间复杂度是就取决于结果的数量了,不再是一个多项式的解法了,有兴趣的朋友可以看看Unique
Binary Search Trees II。
分享到:
相关推荐
sqlite-netFx451-static-binary-bundle-x64-2013-1.0.112.0.zip 下错版本了,官网下的好慢,免费分享
二元树
Trees-Binary-Search-Trees-Challenge-1-Source-code:该项目演示了BST的PreOrder遍历
sqlite-netFx46-binary-bundle-x64-2015-1.0.113.0.zip
Pow(xn) leetcode Binary-Search-3 问题1 Pow(x,n) () 问题2 找到 K 个最近的元素 ()
617.-合并二叉树-递归方法-C-Leetcode 给定两个二叉树 root1 和 root2。 想象一下,当您将其中一个覆盖另一个时,两棵树的某些节点重叠而其他节点不重叠。 您需要将两棵树合并成一个新的二叉树。 合并规则是,如果两...
Binary-Search-1 问题1 搜索二维矩阵() 问题1 在旋转排序数组中搜索 () 问题2 在无限排序数组中搜索: 给定一个未知长度的排序数组和一个要搜索的数字,返回该数字在数组中的索引。 越界访问元素会引发异常。 如果该...
python库,解压后可用。 资源全名:psycopg2_binary-2.8.6-cp38-cp38-win32.whl
psycopg2_binary-2.8.6-cp37-cp37m-manylinux1_x86_64.whl
资源来自pypi官网。 资源全名:talib_binary-0.4.19-cp37-cp37m-manylinux1_x86_64.whl
算法java-BST Java参考中的二进制搜索树
1975年,来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文:Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和阐述的了把空间划分为多个部分的k-d树。
gh-ost-binary-linux-20170914095800.tar 常采用的是对几百万以上的表用pt-online-schema-change,这种方式会产生大量的binlog,业务高峰期不能做,会引起主备延迟,gh-ost有一定优势
Binary-Search-3.1 问题1 优化航线 () 在尝试这个问题之前有 3 件事需要知道: maxTravelDist,它是一个整数,表示给定飞机的最大操作行程距离; forwardRouteList,它是一个整数对列表,其中第一个整数表示前向航线...
Nexus 5 OTA update-binary 和 update-script ,recovery刷机包制作
gh-ost的github下载有时会及其的慢,上传1.0.49到CSDN,有需要的可以来下载。 官方下载地址: ...a1d7f72e1119bb8a939204a56acbee09eb52c769183a4649e56d6b3b524cb774 gh-ost-binary-linux-20200209110835.tar.gz
Binary-Search-2 问题一:() 给定一个按升序排序的整数 nums 数组,找到给定目标值的开始和结束位置。 您的算法的运行时复杂度必须为 O(log n)。 如果在数组中找不到目标,则返回 [-1, -1]。 示例 1: 输入:nums ...
leetcode求交集Binary-Search-4 问题1 两个数组的交集 II () 问题2 两个有序数组的中位数 ()
前端开源库-binary-search-tree二进制搜索树,不同的二进制搜索树实现,包括自平衡树(AVL)