package tree;

import java.util.Arrays;

public class BuildTree {
	public static TreeNode buildTree0(int[] preorder, int[] inorder){
		if(preorder.length == 0 || inorder.length == 0) return null;
		TreeNode root = new TreeNode(preorder[0]);
		int i=0;
		for(i=0; i<inorder.length; i++){
			if (inorder[i] == root.val) break;
		}
		int[] prel = Arrays.copyOfRange(preorder,1  ,i+1);
		int[] prer = Arrays.copyOfRange(preorder,i+1,preorder.length);
		int[] inl  = Arrays.copyOfRange(inorder ,0  ,i);
		int[] inr  = Arrays.copyOfRange(inorder ,i+1,inorder.length);
		
		root.left = buildTree0(prel, inl);
		root.right = buildTree0(prer,inr);
		return root;
	}
	public static TreeNode buildTree1(int[] inorder, int[] postorder){
		if(inorder.length == 0 || postorder.length == 0) return null;
		TreeNode root = new TreeNode(postorder[postorder.length-1]);
		int i=0;
		for(i=0; i<inorder.length; i++){
			if (inorder[i] == root.val) break;
		}
		int[] inl   = Arrays.copyOfRange(inorder ,   0, i);
		int[] inr   = Arrays.copyOfRange(inorder , i+1, inorder.length);
		int[] postl = Arrays.copyOfRange(postorder,  0, i);
		int[] postr = Arrays.copyOfRange(postorder,  i, postorder.length-1);
		
		root.left  = buildTree1(inl,postl);
		root.right = buildTree1(inr,postr);
		return root;
	}
	public static void main(String[] args) {
		int[] preorder  = {1,2,4,7,3,5,6,8};
		int[] inorder   = {4,7,2,1,5,3,8,6};
		int[] postorder = {7,4,2,5,8,6,3,1};
		TreeNode t0 = buildTree0(preorder,  inorder);
		TreeNode t1 = buildTree1(inorder, postorder);
		System.out.println(t0.val + "_" + t1.val);
		System.out.println(t0.right.right.left.val + "_" + t1.right.right.left.val);
	}

}