- 浏览: 593710 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
月光杯:
问题解决了吗?
Exceptions in HDFS -
iostreamin:
神,好厉害,这是我找到的唯一可以ac的Java代码,厉害。
[leetcode] word ladder II -
standalone:
One answer I agree with:引用Whene ...
How many string objects are created? -
DiaoCow:
不错!,一开始对这些确实容易犯迷糊
erlang中的冒号 分号 和 句号 -
standalone:
Exception in thread "main& ...
one java interview question
Problem:
Given numbers 1,2,3...N, print all binary search trees that can be constructed with these N numbers.
Solution:
Result:
Given numbers 1,2,3...N, print all binary search trees that can be constructed with these N numbers.
Solution:
package alg; import java.util.ArrayList; import java.util.Collections; import java.util.List; public class AllBST { class Node<T extends Comparable<?>> { Node<T> left, right; T data; public Node(T data) { this(data, null, null); } public Node(T data, Node<T> l, Node<T> r){ this.data = data; this.left = l; this.right = r; } } class BTreePrinter { public <T extends Comparable<?>> void printNode(Node<T> root) { int maxLevel = maxLevel(root); printNodeInternal(Collections.singletonList(root), 1, maxLevel); } public <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) { if (nodes.isEmpty() || isAllElementsNull(nodes)) return; int floor = maxLevel - level; int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0))); int firstSpaces = (int) Math.pow(2, (floor)) - 1; int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1; printWhitespaces(firstSpaces); List<Node<T>> newNodes = new ArrayList<Node<T>>(); for (Node<T> node : nodes) { if (node != null) { System.out.print(node.data); newNodes.add(node.left); newNodes.add(node.right); } else { newNodes.add(null); newNodes.add(null); System.out.print(" "); } printWhitespaces(betweenSpaces); } System.out.println(""); for (int i = 1; i <= endgeLines; i++) { for (int j = 0; j < nodes.size(); j++) { printWhitespaces(firstSpaces - i); if (nodes.get(j) == null) { printWhitespaces(endgeLines + endgeLines + i + 1); continue; } if (nodes.get(j).left != null) System.out.print("/"); else printWhitespaces(1); printWhitespaces(i + i - 1); if (nodes.get(j).right != null) System.out.print("\\"); else printWhitespaces(1); printWhitespaces(endgeLines + endgeLines - i); } System.out.println(""); } printNodeInternal(newNodes, level + 1, maxLevel); } private void printWhitespaces(int count) { for (int i = 0; i < count; i++) System.out.print(" "); } private <T extends Comparable<?>> int maxLevel(Node<T> node) { if (node == null) return 0; return Math.max(maxLevel(node.left), maxLevel(node.right)) + 1; } private <T> boolean isAllElementsNull(List<T> list) { for (Object object : list) { if (object != null) return false; } return true; } } public ArrayList<Node<Integer>> buildBST(int i, int j){ ArrayList<Node<Integer>> list = new ArrayList<Node<Integer>>(); if(i > j){ return list; }else if(i==j){ Node<Integer> n = new Node<Integer>(i); list.add(n); return list; }else { for(int k=i; k<=j; k++){ ArrayList<Node<Integer>> leftSubTrees = buildBST(i, k-1); ArrayList<Node<Integer>> rightSubTrees = buildBST(k+1, j); if(leftSubTrees.isEmpty()){ for(Node<Integer> r: rightSubTrees){ Node<Integer> subRoot = new Node<Integer>(k, null, r); list.add(subRoot); } }else if(rightSubTrees.isEmpty()){ for(Node<Integer> l: leftSubTrees){ Node<Integer> subRoot = new Node<Integer>(k, l, null); list.add(subRoot); } }else { for(Node<Integer> l: leftSubTrees) for(Node<Integer> r: rightSubTrees){ Node<Integer> subRoot = new Node<Integer>(k, l, r); list.add(subRoot); } } } return list; } } public int calculateAllBstCount(int nodeNum){ int sum = 0; if(nodeNum <= 1){ return 1; } for(int i = 1; i <= nodeNum; i++){ int left = calculateAllBstCount(i-1); int right = calculateAllBstCount(nodeNum - i); sum += left * right; } return sum; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub AllBST bst = new AllBST(); AllBST.BTreePrinter btp = bst.new BTreePrinter(); ArrayList<Node<Integer>> trees = bst.buildBST(1, 6); int total = bst.calculateAllBstCount(6); System.out.println("Total: " + total); int index = 0; for(Node<Integer> root : trees){ System.out.println("result " + index++); btp.printNode(root); System.out.println(""); } } }
Result:
Total: 132 result 0 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 3 \ \ \ \ 4 \ \ 5 \ 6 result 1 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 3 \ \ \ \ 4 \ \ 6 / 5 result 2 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 3 \ \ 5 / \ 4 6 result 3 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 3 \ \ \ \ 6 / / 4 \ 5 result 4 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 3 \ \ \ \ 6 / / 5 / 4 result 5 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 4 / \ / \ 3 5 \ 6 result 6 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 4 / \ / \ 3 6 / 5 result 7 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 5 / \ / \ 3 6 \ 4 result 8 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 5 / \ / \ 4 6 / 3 result 9 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 6 / / / / 3 \ \ 4 \ 5 result 10 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 6 / / / / 3 \ \ 5 / 4 result 11 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 6 / / 4 / \ 3 5 result 12 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 6 / / / / 5 / / 3 \ 4 result 13 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 2 \ \ \ \ \ \ \ \ 6 / / / / 5 / / 4 / 3 result 14 1 \ \ \ \ \ \ \ \ 3 / \ / \ / \ / \ 2 4 \ \ 5 \ 6 result 15 1 \ \ \ \ \ \ \ \ 3 / \ / \ / \ / \ 2 4 \ \ 6 / 5 result 16 1 \ \ \ \ 3 / \ / \ 2 5 / \ 4 6 result 17 1 \ \ \ \ \ \ \ \ 3 / \ / \ / \ / \ 2 6 / / 4 \ 5 result 18 1 \ \ \ \ \ \ \ \ 3 / \ / \ / \ / \ 2 6 / / 5 / 4 result 19 1 \ \ \ \ 4 / \ / \ 2 5 \ \ 3 6 result 20 1 \ \ \ \ 4 / \ / \ 2 6 \ / 3 5 result 21 1 \ \ \ \ 4 / \ / \ 3 5 / \ 2 6 result 22 1 \ \ \ \ 4 / \ / \ 3 6 / / 2 5 result 23 1 \ \ \ \ \ \ \ \ 5 / \ / \ / \ / \ 2 6 \ \ 3 \ 4 result 24 1 \ \ \ \ \ \ \ \ 5 / \ / \ / \ / \ 2 6 \ \ 4 / 3 result 25 1 \ \ \ \ 5 / \ / \ 3 6 / \ 2 4 result 26 1 \ \ \ \ \ \ \ \ 5 / \ / \ / \ / \ 4 6 / / 2 \ 3 result 27 1 \ \ \ \ \ \ \ \ 5 / \ / \ / \ / \ 4 6 / / 3 / 2 result 28 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 2 \ \ \ \ 3 \ \ 4 \ 5 result 29 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 2 \ \ \ \ 3 \ \ 5 / 4 result 30 1 \ \ \ \ \ \ \ \ 6 / / / / 2 \ \ 4 / \ 3 5 result 31 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 2 \ \ \ \ 5 / / 3 \ 4 result 32 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 2 \ \ \ \ 5 / / 4 / 3 result 33 1 \ \ \ \ \ \ \ \ 6 / / / / 3 / \ / \ 2 4 \ 5 result 34 1 \ \ \ \ \ \ \ \ 6 / / / / 3 / \ / \ 2 5 / 4 result 35 1 \ \ \ \ \ \ \ \ 6 / / / / 4 / \ / \ 2 5 \ 3 result 36 1 \ \ \ \ \ \ \ \ 6 / / / / 4 / \ / \ 3 5 / 2 result 37 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 5 / / / / 2 \ \ 3 \ 4 result 38 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 5 / / / / 2 \ \ 4 / 3 result 39 1 \ \ \ \ \ \ \ \ 6 / / / / 5 / / 3 / \ 2 4 result 40 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 5 / / / / 4 / / 2 \ 3 result 41 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6 / / / / / / / / 5 / / / / 4 / / 3 / 2 result 42 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 3 \ \ \ \ 4 \ \ 5 \ 6 result 43 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 3 \ \ \ \ 4 \ \ 6 / 5 result 44 2 / \ / \ / \ / \ 1 3 \ \ 5 / \ 4 6 result 45 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 3 \ \ \ \ 6 / / 4 \ 5 result 46 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 3 \ \ \ \ 6 / / 5 / 4 result 47 2 / \ / \ / \ / \ 1 4 / \ / \ 3 5 \ 6 result 48 2 / \ / \ / \ / \ 1 4 / \ / \ 3 6 / 5 result 49 2 / \ / \ / \ / \ 1 5 / \ / \ 3 6 \ 4 result 50 2 / \ / \ / \ / \ 1 5 / \ / \ 4 6 / 3 result 51 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 / / / / 3 \ \ 4 \ 5 result 52 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 / / / / 3 \ \ 5 / 4 result 53 2 / \ / \ / \ / \ 1 6 / / 4 / \ 3 5 result 54 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 / / / / 5 / / 3 \ 4 result 55 2 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 / / / / 5 / / 4 / 3 result 56 3 / \ / \ / \ / \ 1 4 \ \ \ \ 2 5 \ 6 result 57 3 / \ / \ / \ / \ 1 4 \ \ \ \ 2 6 / 5 result 58 3 / \ / \ 1 5 \ / \ 2 4 6 result 59 3 / \ / \ / \ / \ 1 6 \ / \ / 2 4 \ 5 result 60 3 / \ / \ / \ / \ 1 6 \ / \ / 2 5 / 4 result 61 3 / \ / \ / \ / \ 2 4 / \ / \ 1 5 \ 6 result 62 3 / \ / \ / \ / \ 2 4 / \ / \ 1 6 / 5 result 63 3 / \ / \ 2 5 / / \ 1 4 6 result 64 3 / \ / \ / \ / \ 2 6 / / / / 1 4 \ 5 result 65 3 / \ / \ / \ / \ 2 6 / / / / 1 5 / 4 result 66 4 / \ / \ / \ / \ 1 5 \ \ \ \ 2 6 \ 3 result 67 4 / \ / \ / \ / \ 1 6 \ / \ / 2 5 \ 3 result 68 4 / \ / \ / \ / \ 1 5 \ \ \ \ 3 6 / 2 result 69 4 / \ / \ / \ / \ 1 6 \ / \ / 3 5 / 2 result 70 4 / \ / \ 2 5 / \ \ 1 3 6 result 71 4 / \ / \ 2 6 / \ / 1 3 5 result 72 4 / \ / \ / \ / \ 3 5 / \ / \ 1 6 \ 2 result 73 4 / \ / \ / \ / \ 3 6 / / / / 1 5 \ 2 result 74 4 / \ / \ / \ / \ 3 5 / \ / \ 2 6 / 1 result 75 4 / \ / \ / \ / \ 3 6 / / / / 2 5 / 1 result 76 5 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 \ \ \ \ 2 \ \ 3 \ 4 result 77 5 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 \ \ \ \ 2 \ \ 4 / 3 result 78 5 / \ / \ / \ / \ 1 6 \ \ 3 / \ 2 4 result 79 5 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 \ \ \ \ 4 / / 2 \ 3 result 80 5 / \ / \ / \ / \ / \ / \ / \ / \ 1 6 \ \ \ \ 4 / / 3 / 2 result 81 5 / \ / \ / \ / \ 2 6 / \ / \ 1 3 \ 4 result 82 5 / \ / \ / \ / \ 2 6 / \ / \ 1 4 / 3 result 83 5 / \ / \ / \ / \ 3 6 / \ / \ 1 4 \ 2 result 84 5 / \ / \ / \ / \ 3 6 / \ / \ 2 4 / 1 result 85 5 / \ / \ / \ / \ / \ / \ / \ / \ 4 6 / / / / 1 \ \ 2 \ 3 result 86 5 / \ / \ / \ / \ / \ / \ / \ / \ 4 6 / / / / 1 \ \ 3 / 2 result 87 5 / \ / \ / \ / \ 4 6 / / 2 / \ 1 3 result 88 5 / \ / \ / \ / \ / \ / \ / \ / \ 4 6 / / / / 3 / / 1 \ 2 result 89 5 / \ / \ / \ / \ / \ / \ / \ / \ 4 6 / / / / 3 / / 2 / 1 result 90 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 3 \ \ 4 \ 5 result 91 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 3 \ \ 5 / 4 result 92 6 / / / / / / / / 1 \ \ \ \ 2 \ \ 4 / \ 3 5 result 93 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 5 / / 3 \ 4 result 94 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 2 \ \ \ \ 5 / / 4 / 3 result 95 6 / / / / / / / / 1 \ \ \ \ 3 / \ / \ 2 4 \ 5 result 96 6 / / / / / / / / 1 \ \ \ \ 3 / \ / \ 2 5 / 4 result 97 6 / / / / / / / / 1 \ \ \ \ 4 / \ / \ 2 5 \ 3 result 98 6 / / / / / / / / 1 \ \ \ \ 4 / \ / \ 3 5 / 2 result 99 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 5 / / / / 2 \ \ 3 \ 4 result 100 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 5 / / / / 2 \ \ 4 / 3 result 101 6 / / / / / / / / 1 \ \ \ \ 5 / / 3 / \ 2 4 result 102 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 5 / / / / 4 / / 2 \ 3 result 103 6 / / / / / / / / / / / / / / / / 1 \ \ \ \ \ \ \ \ 5 / / / / 4 / / 3 / 2 result 104 6 / / / / / / / / 2 / \ / \ / \ / \ 1 3 \ \ 4 \ 5 result 105 6 / / / / / / / / 2 / \ / \ / \ / \ 1 3 \ \ 5 / 4 result 106 6 / / / / 2 / \ / \ 1 4 / \ 3 5 result 107 6 / / / / / / / / 2 / \ / \ / \ / \ 1 5 / / 3 \ 4 result 108 6 / / / / / / / / 2 / \ / \ / \ / \ 1 5 / / 4 / 3 result 109 6 / / / / 3 / \ / \ 1 4 \ \ 2 5 result 110 6 / / / / 3 / \ / \ 1 5 \ / 2 4 result 111 6 / / / / 3 / \ / \ 2 4 / \ 1 5 result 112 6 / / / / 3 / \ / \ 2 5 / / 1 4 result 113 6 / / / / / / / / 4 / \ / \ / \ / \ 1 5 \ \ 2 \ 3 result 114 6 / / / / / / / / 4 / \ / \ / \ / \ 1 5 \ \ 3 / 2 result 115 6 / / / / 4 / \ / \ 2 5 / \ 1 3 result 116 6 / / / / / / / / 4 / \ / \ / \ / \ 3 5 / / 1 \ 2 result 117 6 / / / / / / / / 4 / \ / \ / \ / \ 3 5 / / 2 / 1 result 118 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 1 \ \ \ \ 2 \ \ 3 \ 4 result 119 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 1 \ \ \ \ 2 \ \ 4 / 3 result 120 6 / / / / / / / / 5 / / / / 1 \ \ 3 / \ 2 4 result 121 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 1 \ \ \ \ 4 / / 2 \ 3 result 122 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 1 \ \ \ \ 4 / / 3 / 2 result 123 6 / / / / / / / / 5 / / / / 2 / \ / \ 1 3 \ 4 result 124 6 / / / / / / / / 5 / / / / 2 / \ / \ 1 4 / 3 result 125 6 / / / / / / / / 5 / / / / 3 / \ / \ 1 4 \ 2 result 126 6 / / / / / / / / 5 / / / / 3 / \ / \ 2 4 / 1 result 127 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 4 / / / / 1 \ \ 2 \ 3 result 128 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 4 / / / / 1 \ \ 3 / 2 result 129 6 / / / / / / / / 5 / / / / 4 / / 2 / \ 1 3 result 130 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 4 / / / / 3 / / 1 \ 2 result 131 6 / / / / / / / / / / / / / / / / 5 / / / / / / / / 4 / / / / 3 / / 2 / 1
发表评论
-
ssl 与 java 实例
2014-01-27 10:10 744http://www.iteye.com/topic/1125 ... -
Java NIO
2014-01-10 21:28 694看了这个java nio的教程,明白了什么是Selector. ... -
再谈Java的wait(), sleep(), notify()和notifyAll()
2013-07-25 10:59 1867一段时间不用java,这些概念就全混淆了,有必要彻底澄清一下, ... -
Why singleton is anti-pattern?
2013-07-03 10:12 866OO Test Other reasons? -
How to generate the serialVersionUID when you implement Serializable interface,j
2013-07-01 10:52 915http://docs.oracle.com/javase/6 ... -
Java Override的两个问题
2013-06-01 11:40 9231: 如果子类中的方法的参数是父类的方法的子类型,那么算不算o ... -
Java常用类API统计
2013-06-01 11:35 0String charAt(int) compareTo( ... -
How many string objects are created?
2013-06-01 10:18 1308This is a very common java inte ... -
使用Java的DelayQueue容易碰到的一个坑
2013-05-27 17:32 6640今天不忙,学习一下java.util.concurrent.D ... -
[leetcode] Decode ways
2013-05-02 21:47 1386http://leetcode.com/onlinejudge ... -
[leetcode] Balanced Binary Tree
2013-04-28 14:08 1558Check if a binary tree is balan ... -
[leetcode] find median of two sorted arrays
2013-04-26 10:55 1429http://leetcode.com/onlinejudge ... -
[leetcode] word ladder
2013-04-25 15:05 2252Q: Given two words (start and ... -
[leetcode] sqrt(x)
2013-04-15 07:44 2420I have talked about this questi ... -
[leetcode] word ladder II
2013-04-15 07:35 11624http://leetcode.com/onlinejudge ... -
[leetcode] Count and Say
2013-04-12 14:05 2236http://leetcode.com/onlinejudge ... -
Date/Time处理函数总结 [To Do]
2013-04-12 10:46 633几种我所用到的用来处理日期,时间的函数总结。 Perl 1 ... -
[leetcode] Palindrome Partition
2013-04-12 10:25 1300http://leetcode.com/onlinejudge ... -
[leetcode] Palindrome Partitioning II
2013-04-11 16:45 1485http://leetcode.com/onlinejudge ... -
Profiling your Java code using Spring
2013-03-05 15:02 659Quite good article!!! http://w ...
相关推荐
1975年,来自斯坦福大学的Jon Louis Bentley在ACM杂志上发表的一篇论文:Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和阐述的了把空间划分为多个部分的k-d树。
Self-Adjusting Binary Search TreesDANIEL DOMINIC SLEATOR... On an n-node splay tree, all the standard search tree operations have an amortized time bound of @log n) per operation, where by “amortized t
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。对数据向量中的值进行二进制搜索。
matlab开发-Binarysearch。bsearch对已排序的数组执行二进制搜索
binary trees, description and implementation
最小成本二分检索树optimal binary optimal binary
Binary Search Tree 利用C++實現 Binary Search Tree
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 ...
实现折半查找的程序 希望大家功能学习,共同进步
关于最优二叉查找树的开山之作,介绍了最优二叉查找树的概念,以及构造最优二叉查找树的动态规划算法,来自D. E. KNUTH,发表于1971年,亦可从这里下载:...
二元树
NULL 博文链接:https://enria.iteye.com/blog/1441105
Java Methods-Binary Trees.ppt
binary search tree program using c language
CatCafe:我正在进行的一个项目是使用Java Binary Search Trees,递归和Tree Traversal提出由三叉树CatTree代表的猫的数据库
binarysearch.py
http://blog.csdn.net/xkzju2010/article/details/46399155
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. ...