- 关于二叉树的前中后序遍历的很好一道题
-
题目:根据二叉树的前序和中序序列来重建二叉树,输出其后序序列
image.png - 来看看代码描述
package someTest;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
public class POJ2255 {
private static String last;
//构建二叉树,并返回根节点
private static Node1 constructCore(String before,String middle) {
if("".equals(before)||"".equals(middle)||before.length()<0) {
return null;
}
Node1 root=new Node1();
char temp=before.charAt(0);
int rootMiddleIndex=middle.indexOf(temp);
root.value=temp;
root.left=constructCore(before.substring(1, rootMiddleIndex)+1, middle.substring(0, rootMiddleIndex));
root.right=constructCore(before.substring(rootMiddleIndex+1), middle.substring(rootMiddleIndex)+1);
return root;
}
//后序遍历
private static void lastOrder(Node1 root) {
if(root==null) {
return;
}
lastOrder(root.left);
lastOrder(root.right);
last+=root.value;
}
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
String before;
String middle;
while (in.hasNext()) {
before = in.next();
middle = in.next();
Node1 root = constructCore(before, middle); // 重建之后的二叉树根结点
last = "";
lastOrder(root);
out.println(last);
}
out.flush();
}
}
class Node1{
public Node1 left;
public Node1 right;
public char value;
}
网友评论