https://vjudge.net/PRoblem/UVA-548

You are to determine the value of the leaf node in a given binary tree that is the terminal node of apath of least value from the root of the binary tree to any leaf. The value of a path is the sum of valuesof nodes along that path.

Input

The input file will contain a description of the binary tree given as the inorder and postorder traversalsequences of that tree. Your program will read two line (until end of file) from the input file. The firstline will contain the sequence of values associated with an inorder traversal of the tree and the secondline will contain the sequence of values associated with a postorder traversal of the tree. All valueswill be different, greater than zero and less than 10000. You may assume that no binary tree will havemore than 10000 nodes or less than 1 node.

Output

For each tree description you should output the value of the leaf node of a path of least value. In thecase of multiple paths of least value you should pick the one with the least value on the terminal node.

Sample Input

3 2 1 4 5 7 6

3 1 2 5 6 7 4

7 8 11 3 5 16 12 18

8 3 11 7 16 18 12 5

255

255

Sample Output

1

3

255

思路:這道題分為兩個部分：

第一部分是根據二叉樹的中序遍歷和后序遍歷建立二叉樹。

第二部分是根據建立好的二叉樹運用DFS搜索出從根節點到葉子結點的節點之和最小的路徑，并輸出路徑的葉子結點。

建樹的過程很簡單，根據后序遍歷的性質，即從末尾向前遇到的節點為根節點，然后再中序遍歷中找到根節點對應的下標i,然后遞歸的調用建樹過程即可，值得注意的是，因為后序遍歷是線性查找，因此可以用全局變量index，只需動態維護一個index即可，具體實現細節可看代碼

關鍵的是搜索的過程，首先用全局變量sum記錄每條路徑中的最小值，singSum記錄單條路徑的值,ans記錄最短路徑對應的葉子結點的值。

PS：遞歸結束后注意對singSum變量進行回溯處理。

import java.util.Scanner;import java.util.Vector;public class Main {	private static int index;	private static int sum,ans,singSum;	public static void main(String[] args) {		Scanner scan = new Scanner(System.in);		while(scan.hasNext()){			String a = scan.nextLine();			String b = scan.nextLine();			String[] aa = a.split(" ");			String[] bb = b.split(" ");			Vector<Integer> inorder = new Vector<Integer>();			Vector<Integer> postorder = new Vector<Integer>();			for(int i=0;i<aa.length;i++){				inorder.add(Integer.valueOf(aa[i]));			}			for(int i=0;i<bb.length;i++){				postorder.add(Integer.valueOf(bb[i]));			}			index = inorder.size()-1;			Node root = buildTree(inorder,postorder,0,index);			sum = Integer.MAX_VALUE;//所有路徑最小值			ans = 0;//最短路徑的葉子結點的權值			singSum = 0;//單挑路徑和			dfs(root);			System.out.println(ans);//輸出結果		}	}		//搜索	public static void dfs(Node root){		if(root!=null){			//System.out.print(root.v+" ");			if(root.left==null&&root.right==null){				singSum+=root.v;				//System.out.println(singSum+",v=="+root.v);				if(sum>singSum){					sum = singSum;					ans = root.v;				}				singSum-=root.v;			}			if(root.left!=null){				singSum+=root.v;//遞歸				dfs(root.left);				singSum-=root.v;//回溯			}			if(root.right!=null){				singSum+=root.v;//遞歸				dfs(root.right);				singSum-=root.v;//回溯			}		}	}	//遞歸建樹	public static Node buildTree(Vector<Integer> inorder,Vector<Integer> postorder,int start,int end){		int v = postorder.get(index);		int i = start;		for(;i<=end;i++){			if(inorder.get(i)==v)				break;		}		Node root = new Node(v);		//注意:先右子樹，后左子樹		if(i+1<=end){			index--;//根節點下表減1			root.right = buildTree(inorder,postorder,i+1,end);		}		if(i-1>=start){			index--;//根節點下表減1			root.left = buildTree(inorder,postorder,start,i-1);		}		return root;	}	//節點	static class Node{		int v;		Node left,right;		public Node(int v){			this.v = v;			left = null;			right = null;		}	}}