根据先序遍历和中序遍历求后序遍历
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNext()){ String pre = scan.next(); String mid = scan.next(); Node root = build(pre,mid,0,pre.length()-1,0,mid.length()-1); dfs(root); System.out.println(); } } public static void dfs(Node root){ if(root!=null){ if(root.left!=null){ dfs(root.left); } if(root.right!=null){ dfs(root.right); } System.out.print(root.c); } } public static Node build(String pre,String mid,int pre1,int pre2,int mid1,int mid2){ if(pre1>pre2||mid1>mid2)return null; char c = pre.charAt(pre1); Node root = new Node(); root.c = c; int p = 0; while(mid.charAt(p)!=c)p++; int cnt = p-mid1; root.left = build(pre,mid,pre1+1,pre1+cnt,mid1,p-1); root.right = build(pre,mid,pre1+cnt+1,pre2,p+1,mid2); return root; } static class Node{ char c; Node left,right; } }
