POJ|POJ 2255 Tree Recovery（根据前中序遍历，重建二叉树并求后序遍历） POJ2255TreeRecovery（根据前中序遍

【POJ|POJ 2255 Tree Recovery（根据前中序遍历，重建二叉树并求后序遍历）】题意：给出二叉树的前序遍历和中序遍历，求后序遍历。
NO.1：无需重建二叉树，可直接求出后序遍历结果。

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 Main {private static String last = ""; // 保存后序遍历结果private static void getLate(String before, String middle) { // 递归终点 if ("".equals(before) || "".equals(middle) || (middle.indexOf(before.charAt(0)) < 0)) { return; } char temp = before.charAt(0); // 获取根结点 int rootMiddleIndex = middle.indexOf(temp); // 获取根结点在中序遍历的位置下标 // 递归左子树 getLate(before.substring(1, rootMiddleIndex + 1), middle.substring(0, rootMiddleIndex)); // 递归右子树 getLate(before.substring(rootMiddleIndex + 1), middle.substring(rootMiddleIndex + 1)); // 后序遍历结果：左右中 last += temp; }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(); last = ""; getLate(before, middle); out.println(last); } out.flush(); } }

NO.2 重建二叉树

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 Main {private static String last; // 构建二叉树，并返回根节点 private static Node constructCore(String before, String middle) { if ("".equals(before) || "".equals(middle) || before.length() < 0) { return null; } Node root = new Node(); char temp = before.charAt(0); int rootMiddleIndex = middle.indexOf(temp); root.value = https://www.it610.com/article/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(Node 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(); Node root = constructCore(before, middle); // 重建之后的二叉树根结点 last =""; lastOrder(root); out.println(last); } out.flush(); }}class Node { public Node left; public Node right; public char value; }