新博文地址:[leetcode]Unique Binary Search Trees II
Unique Binary Search Trees II
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
这道题看起来真的挺唬人的。但是搞明白之后还算好,提示中说用DP,但是还是用了DFS,总是感觉DP没法做,可能还是DP不熟吧。
思想是模拟人工建树的过程:
首先,一个节点时,已经好了。
n个节点时候(n > 1),第一个节点的左子树一定为空,同理最后一个节点的右子树一定为空。那么中间节点呢,假设中间节点为k(1<k<n),1~k-1是其左子树,k+1~n是其右子树,然后递归实现1~k-1和k+1~n,典型的分治策略。
List<TreeNode> result = new ArrayList<TreeNode>(); public List<TreeNode> generateTrees(int n) { if (n <= 0) { result.add(null);//坑爹啊,非要加个null,加你妹啊!!! return result; } return generateSubTree(1, n); } private List<TreeNode> generateSubTree(int begin,int end) { if (begin == end) { List<TreeNode> leaf = new ArrayList<TreeNode>(); leaf.add(new TreeNode(begin)); return leaf; } List<TreeNode> list = new ArrayList<TreeNode>(); for (int i = begin; i <= end; i++) { if (i == begin) { List<TreeNode> right = generateSubTree(i + 1, end); for (TreeNode tem : right) { TreeNode node = new TreeNode(i); node.right = tem; list.add(node); } } else if (i == end) { List<TreeNode> left = generateSubTree( begin, end - 1); for (TreeNode tem : left) { TreeNode node = new TreeNode(i); node.left = tem; list.add(node); } } else { List<TreeNode> left = generateSubTree( begin, i - 1); List<TreeNode> right = generateSubTree( i + 1, end); for (TreeNode temLeft : left) { for (TreeNode temRight : right) { TreeNode node = new TreeNode(i); node.left = temLeft; node.right = temRight; list.add(node); } } } } return list; }
我去,看了别人的代码,貌似都是清一色的分治法,只不过人家的代码简洁多了,果然自己是渣渣
相关推荐
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 ...
A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value, by comparing an ...
matlab开发-BinarySearch。对数据向量中的值进行二进制搜索。
Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled ...
matlab开发-Binarysearch。bsearch对已排序的数组执行二进制搜索
最小成本二分检索树optimal binary optimal binary
Binary Search Tree 利用C++實現 Binary Search Tree
binary trees, description and implementation
实现折半查找的程序 希望大家功能学习,共同进步
关于最优二叉查找树的开山之作,介绍了最优二叉查找树的概念,以及构造最优二叉查找树的动态规划算法,来自D. E. KNUTH,发表于1971年,亦可从这里下载:...
二元树
NULL 博文链接:https://enria.iteye.com/blog/1441105
CatCafe:我正在进行的一个项目是使用Java Binary Search Trees,递归和Tree Traversal提出由三叉树CatTree代表的猫的数据库
binary search tree program using c language
Java Methods-Binary Trees.ppt
http://blog.csdn.net/xkzju2010/article/details/46399155
binarysearch.py
The most commonly used binary search variant was first published by Hermann Bottenbruch in 1962 and hasn't notably changed since. Below I'll describe several novel variants with improved performance. ...