Poj 2255 Tree Recovery

• 关于二叉树的前中后序遍历的很好一道题

• 题目：根据二叉树的前序和中序序列来重建二叉树，输出其后序序列

  
  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;
}