2013
12-12

# 九度-1078-二叉树遍历[解题代码]

ABC
BAC
FDXEAG
XDEFAG

BCA
XEDGAF

java 代码如下：
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
static String str1,str2;
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedInputStream(System.in));
while(s.hasNext()){
str1 = s.next();
str2 = s.next();
Node root = creatTree(str1,str2);
lastSee(root);
System.out.println();
}

}

static void lastSee(Node tree){
if(tree == null)return;
lastSee(tree.l);
lastSee(tree.r);
System.out.print(tree.data);
}
static Node creatTree(String s1,String s2){
Node n = null;
if(s1 == null || s2==null)
return null;
String left2 = null,right2 = null,news1 = null,news2 = null;
int len1 = 0;
char root = s1.charAt(0);
int index=s2.indexOf(root);
if(index>0){
left2 = s2.substring(0,index);
len1 = left2.length();
}
if(index<s2.length()-1)
right2 = s2.substring(index+1);
news1 = s1.substring(1, 1+len1);
news2 = s1.substring(1+len1);
n = new Node(creatTree(news1,left2),creatTree(news2,right2),s1.charAt(0));
return n;
}
}

class Node{
Node l;
Node r;
char data;
public Node(Node l, Node r, char data) {
this.l = l;
this.r = r;
this.data = data;
}

}

/**************************************************************
Problem: 1078
User: coder
Language: Java
Result: Accepted
Time:170 ms
Memory:15896 kb
****************************************************************/

1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。