2013
11-09

# Falling Leaves

Figure 1

Figure 1 shows a graphical representation of a binary tree of letters. People familiar with binary trees can skip over the definitions of a binary tree of letters, leaves of a binary tree, and a binary search tree of letters, and go right to The problem.

A binary tree of letters may be one of two things:

1. It may be empty.
2. It may have a root node. A node has a letter as data and refers to a left and a right subtree. The left and right subtrees are also binary trees of letters.

In the graphical representation of a binary tree of letters:

1. Empty trees are omitted completely.
2. Each node is indicated by
• Its letter data,
• A line segment down to the left to the left subtree, if the left subtree is nonempty,
• A line segment down to the right to the right subtree, if the right subtree is nonempty.

A leaf in a binary tree is a node whose subtrees are both empty. In the example in Figure 1, this would be the five nodes with data B, D, H, P, and Y.

The preorder traversal of a tree of letters satisfies the defining properties:

1. If the tree is empty, then the preorder traversal is empty.
2. If the tree is not empty, then the preorder traversal consists of the following, in order
• The data from the root node,
• The preorder traversal of the root’s left subtree,
• The preorder traversal of the root’s right subtree.

The preorder traversal of the tree in Figure 1 is KGCBDHQMPY.

A tree like the one in Figure 1 is also a binary search tree of letters. A binary search tree of letters is a binary tree of letters in which each node satisfies:

The root’s data comes later in the alphabet than all the data in the nodes in the left subtree.

The root’s data comes earlier in the alphabet than all the data in the nodes in the right subtree.

The problem:

Consider the following sequence of operations on a binary search tree of letters

Remove the leaves and list the data removed

Repeat this procedure until the tree is empty

Starting from the tree below on the left, we produce the sequence of trees shown, and then the empty tree

by removing the leaves with data

BDHPY

CM

GQ

K

Your problem is to start with such a sequence of lines of leaves from a binary search tree of letters and output the preorder traversal of the tree.

The input will contain one or more data sets. Each data set is a sequence of one or more lines of capital letters.

The lines contain the leaves removed from a binary search tree in the stages described above. The letters on a line will be listed in increasing alphabetical order. Data sets are separated by a line containing only an asterisk (‘*’).

The last data set is followed by a line containing only a dollar sign (‘$’). There are no blanks or empty lines in the input. 输出: For each input data set, there is a unique binary search tree that would produce the sequence of leaves. The output is a line containing only the preorder traversal of that tree, with no blanks. 样例输入: BDHPY CM GQ K * AC B$

KGCBDHQMPY
BAC

//* @author: SmilingWang
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in =new Scanner(System.in);
BinarySearchTree< Character> bt = new BinarySearchTree< Character>();
boolean stop = false;
while(true){
String input = in.next();

LinkedList< String> list = new LinkedList< String>();
while(input.charAt(0) != '*'){
if(input.charAt(0) == '\$'){
stop = true;
break;
}
list.addFirst(input);
input = in.next();
}

for(int i = 0; i < list.size(); i++){
input = list.get(i);
for(int j = 0; j < input.length(); j++){
bt.insert((Character)input.charAt(j));
}
}
bt.printTree();
if(stop){
return;
}
System.out.println();
bt = new BinarySearchTree< Character>();
}
}

}

class BinaryNode< T extends Comparable< ? super T>> {
BinaryNode< T> left;
BinaryNode< T> right;
T element;

public BinaryNode(T theElement){
this(theElement, null, null);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
element = theElement;
left = lt;
right = rt;
}
public T getElement(){
return this.element;
}
public BinaryNode< T> getLeft(){
return this.left;
}
public BinaryNode< T> getRight(){
return this.right;
}
public String toString(){
return element + "";
}
}

class BinarySearchTree< T extends Comparable< ? super T>>{
private BinaryNode< T> root;

public BinarySearchTree(){
root = null;
}
public BinarySearchTree(BinaryNode< T> t){
root = t;
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
public T find(T x){
return elementAt(find(x, root));
}

public void insert(T x){
root = insert(x, root);
}
public void printTree(){
printTree(root);
}

private T elementAt(BinaryNode< T> t){
return t.element;
}
private BinaryNode< T> find(T x, BinaryNode< T> t){
if(t == null){
return null;
}
if(x.compareTo(t.element) < 0){
return find(x, t.left);
}
else if(x.compareTo(t.element) == 0){
return t;
}
else{
return find(x, t.right);
}
}

private BinaryNode< T> insert(T x, BinaryNode< T> t){
if(t == null){
t = new BinaryNode< T>(x, null, null);
}
else if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left);
}
else if(x.compareTo(t.element) > 0){
t.right = insert(x, t.right);
}
else;
return t;
}
private void printTree(BinaryNode< T> t){
if(t != null){
System.out.print(t.element);
printTree(t.left);
printTree(t.right);
}
}

}

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

2. 第二个方法挺不错。NewHead代表新的头节点，通过递归找到最后一个节点之后，就把这个节点赋给NewHead，然后一直返回返回，中途这个值是没有变化的，一边返回一边把相应的指针方向颠倒，最后结束时返回新的头节点到主函数。