2013
11-11

# Tree Recovery

Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes.

This is an example of one of her creations:
                                               D
/ \
/   \
B     E
/ \     \
/   \     \
A     C     G
/
/
F


To record her trees for future generations, she wrote down two strings for each tree: a preorder traversal (root, left subtree, right subtree) and an inorder traversal (left subtree, root, right subtree). For the tree drawn above the preorder traversal is DBACEGF and the inorder traversal is ABCDEFG.

She thought that such a pair of strings would give enough information to reconstruct the tree later (but she never tried it).

Now, years later, looking again at the strings, she realized that reconstructing the trees was indeed possible, but only because she never had used the same letter twice in the same tree.

However, doing the reconstruction by hand, soon turned out to be tedious.

So now she asks you to write a program that does the job for her!

The input will contain one or more test cases.

Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)

Input is terminated by end of file.

For each test case, recover Valentine’s binary tree and print one line containing the tree’s postorder traversal (left subtree, right subtree, root).

DBACEGF ABCDEFG


ACBFGED
CDAB


import java.util.Scanner;

public class Main {

private static char[] seq = new char[100];
private static int s = -1;

public static void getPostOrder(String pre, String in) {
if (pre.length() == 1 && in.length() == 1) {
seq[++s] = in.charAt(0);
// seq[++s] = pre.charAt(0);
return;
}

char root = pre.charAt(0);
seq[++s] = root;

int rootIndex = in.indexOf(root);
if (rootIndex == 0) {
getPostOrder(pre.substring(1), in.substring(1));
return;
} else if (rootIndex == in.length() - 1) {
getPostOrder(pre.substring(1), in.substring(0, in.length() - 1));
return;
} else {
String in_Left = in.substring(0, rootIndex);
String in_Right = in.substring(rootIndex + 1);

int indexLeft = -1;
for (int i = 0; i < in_Left.length(); i++) {
int temp = pre.indexOf(in_Left.charAt(i));
if (temp > indexLeft)
indexLeft = temp;
}

if (in_Right.length() == 1) {
seq[++s] = in_Right.charAt(0);
// return;
} else {
String pre_Right = null;
pre_Right = pre.substring(indexLeft + 1);
getPostOrder(pre_Right, in_Right);
}

if (in_Left.length() == 1) {
seq[++s] = in_Left.charAt(0);
return;
} else {
String pre_Left = null;
pre_Left = pre.substring(1, indexLeft + 1);
getPostOrder(pre_Left, in_Left);
}

}

}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {
s = -1;

String pre = sc.next();
String in = sc.next();

seq = new char[pre.length() + 1];
getPostOrder(pre.trim(), in.trim());

while (s >= 0) {
System.out.print(seq[s--]);
}
System.out.println();
}
}

}

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

2. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？

3. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

4. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

5. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮