package code;


/**
 * @author Clover
 *
 * 2015年4月10日
 */
public class Code106 {

	/*
	 * 已知二叉树的后续遍历和中序遍历,构建出二叉树
	 * 递归求解,好写。
	 * 看代码
	 *
	 */
 public TreeNode buildTree(int[] inorder, int[] postorder) {
 	/*
 	 * 只有一个元素,直接返回自己
 	 */
 	int n=inorder.length;
 	TreeNode p=new TreeNode(postorder[n-1]);
 	
 	if(n==1){
 		return p;
 	}
 	int i;
 	for(i=0;i<n;i++){
 		if(inorder[i]==postorder[n-1])
 			break;
 	}
 	/*
 	 * 构建左子树
 	 */
 	//有左子树
 	if(i>0){
 		int[] leftInorder=new int[i];
 		int[] leftPostorder=new int[i];
 		for(int j=0;j<i;j++){
 			leftInorder[j]=inorder[j];
 			leftPostorder[j]=postorder[j];
 		}
 		p.left=buildTree(leftInorder,leftPostorder);
 	}
 	/*
 	 * 构建右子树
 	 * 如果存在右子树的话
 	 */
 	if(i<n-1){
 		int[] rightInorder=new int[n-i-1];
 		int[] rightPostorder=new int[n-i-1];
 		for(int j=i+1;j<n;j++){
 			rightInorder[j-i-1]=inorder[j];
 			rightPostorder[j-i-1]=postorder[j-1];
 		}
 		p.right=buildTree(rightInorder,rightPostorder);
 	}
		return p;
 }
 
 public void dfs(TreeNode p){
 	System.out.println(p.val);
 	if(p.left!=null)
 		dfs(p.left);
 	if(p.right!=null)
 		dfs(p.right);
 }
 public static void main(String[] args){
 	Code106 code=new Code106();
 	int[] postorder={4,5,2,6,7,3,1};
 	int[] inorder={4,2,5,1,6,3,7};
// 	int[] postorder={4,5,2};
// 	int[] inorder={4,2,5};
 	TreeNode root=code.buildTree(inorder, postorder);
 	code.dfs(root);
 }
 
}