原题链接:http://oj.leetcode.com/problems/unique-binary-search-trees-ii/这道题是求解所有可行的二叉查找树,从Unique
Binary Search Trees中我们已经知道,可行的二叉查找树的数量是相应的卡特兰数,不是一个多项式时间的数量级,所以我们要求解所有的树,自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解,也就是N-Queens中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根,然后递归求解左右子树的所有结果,最后根据左右子树的返回的所有子树,依次选取然后接上(每个左边的子树跟所有右边的子树匹配,而每个右边的子树也要跟所有的左边子树匹配,总共有左右子树数量的乘积种情况),构造好之后作为当前树的结果返回。代码如下:public ArrayList<TreeNode> generateTrees(int n) {
return helper(1,n);
}
private ArrayList<TreeNode> helper(int left, int right)
{
ArrayList<TreeNode> res = new ArrayList<TreeNode>();
if(left>right)
{
res.add(null);
return res;
}
for(int i=left;i<=right;i++)
{
ArrayList<TreeNode> leftList = helper(left,i-1);
ArrayList<TreeNode> rightList = helper(i+1,right);
for(int j=0;j<leftList.size();j++)
{
for(int k=0;k<rightList.size();k++)
{
TreeNode root = new TreeNode(i);
root.left = leftList.get(j);
root.right = rightList.get(k);
res.add(root);
}
}
}
return res;
}
实现中还是有一些细节的,因为构造树时两边要遍历所有左右的匹配,然后接到根上面。当然我们也可以像在Unique
Binary Search Trees中那样存储所有的子树历史信息,然后进行拼合,虽然可以省一些时间,但是最终还是逃不过每个结果要一次运算,时间复杂度还是非多项式的,并且要耗费大量的空间,感觉这样的意义就不是很大了。
分享到:
相关推荐
sqlite-netFx40-static-binary-x64-2010-1.0.112.0.zip;混合编译,支持32位和64位。
sqlite framework 4.6 版本, sqlite-netFx46-binary-x64-2015-1.0.106.0.zip
1975年,来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文:Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和阐述的了把空间划分为多个部分的k-d树。
Self-Adjusting Binary Search TreesDANIEL DOMINIC SLEATOR A N D ROBERT ENDRE TARJANA T&T Bell Laboratories, Murray Hill, NJAbstract. The splay tree, a self-adjusting form of binary search tree, is ...
sqlite framework 4.0 版本, sqlite-netFx40-binary-x64-2010-1.0.106.0.zip
Trees-Binary-Search-Trees-Challenge-1-Source-code:该项目演示了BST的PreOrder遍历
leetcode 2 和 c 617.-合并二叉树-递归方法-C-Leetcode 给定两个二叉树 root1 和 root2。 想象一下,当您将其中一个覆盖另一个时,两棵树的某些节点重叠而其他节点不重叠。 您需要将两棵树合并成一个新的二叉树。 ...
Pow(xn) leetcode Binary-Search-3 问题1 Pow(x,n) () 问题2 找到 K 个最近的元素 ()
sqlite-netFx40-binary-x64-2010-1.0.94.0.zip sqlite 64操作系统api dll,官方很难下载,在这提供方便下载。
Binary-Search-1 问题1 搜索二维矩阵() 问题1 在旋转排序数组中搜索 () 问题2 在无限排序数组中搜索: 给定一个未知长度的排序数组和一个要搜索的数字,返回该数字在数组中的索引。 越界访问元素会引发异常。 如果该...
leetcode 答案leetcode 的工具 这个项目提供了一些工具来更容易地测试 leetcode 答案。 树:切片 <-> TreeNode 此工具有助于将切片转换为 TreeNode,反之亦然。 Slice2TreeNode: []interface{} -> *model....
支持sqlite 数据块加密解密插件。解压文件,将里面的SQLite.Interop.dll拷贝到SQLiteExpert的安装目录然后启动SQLiteExpert,Tools->Options->SQLite library,选择带SQLite.Interop.dll的项即可。
92.reverse-linked-list-ii (反转链表 II) 94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-...
示例1输入: 1 1**示例2**输入: 1 1代码实现Definition for a binary tree node.本文链接: https://www.
leetcode 树节点leetcode 226 - 反转二叉树 方法一:递归 C# public TreeNode InvertTree ( TreeNode root ) { if ( root == null ) return root ; var temp = root . left ; root . left = root . right ; root . ...
sqlite 库,包含所有的dll文件,解压文件,将里面的SQLite.Interop.dll拷贝到SQLiteExpert的安装目录。
示例解题思路最大的深度是左子树或右子树中深度中更大的一个+1,递归的在子树的子树中寻找代码实现Definition for a binary tree node
sqlite framework 4.5.1 版本, sqlite-netFx451-binary-x64-2013-1.0.106.0.zip
wince设备使用sqlite数据库必备资源,需要 .NET Compact Framework 3.5,基于sqlite3;如果你的项目基于 .NET Compact Framework 2.0,请下载我另一个资源1.0.66版本。
leetcode卡leetcode 二叉树卡片 LeetCode 二叉树卡片问题的章节智解