2013
11-09

# Pre-Post-erous!

We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below:
    a   a   a   a
/   /     \   \
b   b       b   b
/     \     /     \
c       c   c       c


All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well.

Input will consist of multiple problem instances. Each instance will consist of a line of the form

m s1 s2

indicating that the trees are m-ary trees, s1 is the pre-order traversal and s2 is the post-order traversal.All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1 <= m <= 20 and the length of s1 and s2 will be between 1 and 26 inclusive. If the length of s1 is k (which is the same as the length of s2, of course), the first k letters of the alphabet will be used in the strings. An input line of 0 will terminate the input.

For each problem instance, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instance. All output values will be within the range of a 32-bit signed integer. For each problem instance, you are guaranteed that there is at least one tree with the given pre-order and post-order traversals.

2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
0

4
1
45
207352860

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
static Scanner cin;
public static void main(String args[]){
cin = new Scanner(System.in);
while(run()==true)
;
}

static boolean run(){
int n = cin.nextInt();
if(n==0)
return false;

Tree tree = new Tree(n, cin.next(), cin.next());
System.out.println(tree.compute());
return true;
}
}

class Tree{
static String preMap, postMap;
static int M;

static int[][] C;

int preStart, postStart, length;

public Tree(int M, String preMap, String postMap){
this.M = M;
this.preMap = preMap;
this.postMap = postMap;

C = new int[100][100];
initialC();

preStart = 0;
postStart  = 0;
length   = preMap.length();
}

public Tree(int preStart, int postStart, int length){
this.preStart = preStart;
this.postStart  = postStart;
this.length = length;
}

ArrayList< Tree> subTree(){
ArrayList< Tree> nodes = new ArrayList< Tree>();

int start = preStart+1;
int pEnd = postStart-1;
int pstart, subLength;

while(start< (preStart+length)){
pstart = pEnd+1;
pEnd  = postMap.indexOf(preMap.charAt(start));
subLength = pEnd-pstart+1;

nodes.add(new Tree(start, pstart, subLength));

start = start+subLength;
}

return nodes;
}

int compute(){
ArrayList< Tree> nodes = subTree();
int count = C(M, nodes.size());
for(Tree t:nodes)
count *= t.compute();
return count;
}

void initialC(){
int i,j;
for(i=0;i< 100;i++)
for(j=0;j< 100;j++)
C[i][j] = -1;

for(i=0;i< 100;i++){
C[1][i] = (i>1? 0:1);
C[i][0] = 1;
}
}

int C(int n, int m){
if(C[n][m] == -1)
return C(n-1, m)+C(n-1, m-1);
else
return C[n][m];
}
}

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

3. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

4. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c