uva 548 Tree (根据中序遍历和后序遍历求先序遍历)

import java.util.Scanner; public class Main { static Scanner scan = new Scanner(System.in); static int best_sum = 0; static int best = 0; public static void main(String[] args) { while(scan.hasNext()){ String mid = scan.nextLine(); String post = scan.nextLine(); String[] aa = mid.split(" "); String[] bb = post.split(" "); int[] midOrder = new int[aa.length]; int[] postOrder = new int[aa.length]; for(int i=0;i<aa.length;i++){ midOrder[i] = Integer.parseInt(aa[i]); postOrder[i] = Integer.parseInt(bb[i]); } Node root = build(midOrder,postOrder,0,midOrder.length-1,0,postOrder.length-1); best_sum = Integer.MAX_VALUE; best = Integer.MAX_VALUE; Pre(root,0); System.out.println(best); } } //先序递归求最优解 public static void Pre(Node root,int sum){ if(root!=null){ sum+=root.value; if(root.left==null&&root.right==null){ if(sum<best_sum||(sum==best_sum&&root.value<best)){ best_sum = sum; best = root.value; } } if(root.left!=null)Pre(root.left,sum); if(root.right!=null)Pre(root.right,sum); } } //根据中序和后序建树 public static Node build(int[] m,int[] p,int m1,int m2,int p1,int p2){ if(m1>m2||p1>p2)return null; Node root = new Node(); int v = p[p2]; root.value = v; int rootIndex = 0; while(m[rootIndex]!=v)rootIndex++; int cnt = rootIndex-m1; root.left = build(m,p,m1,rootIndex-1,p1,p1+cnt-1); root.right = build(m,p,rootIndex+1,m2,p1+cnt,p2-1); return root; } static class Node{ int value; Node left,right; } }