package com.ds.binTree;

class TreeNode{
	private StringBuilder sb = new StringBuilder();
	public int value;
	public TreeNode left,right;
	private String toString(String prefix) {
		sb.append(prefix).append(value).append('\n');
		if(left!=null)
			sb.append(left.toString(prefix + "-L"));
		if(right!=null)
			sb.append(right.toString(prefix + "-R"));
		return sb.toString();
	}
	public String toString() {
		return toString("");
	}
}

public class RebuildBinTree {
	
	static int[] preOrder = {7,6,4,3,5,2,1};
	static int[] midOrder = {4,6,3,7,2,5,1};
	/**
	 * 找到数字a在数组array中的位置
	 * @param a 数字
	 * @param array 数组
	 * @return
	 */
	public static int pos(int a, int[] array) {
		for(int i=0;i<array.length;i++) {
			//System.out.println(a + " Searching...");
			if(array[i]==a) return i;
		}
		System.out.println(a + " not found!");
		return -1;
	}
	/**
	 * 重建二叉树
	 * @param root 根节点
	 * @param preOst 先序遍历数组的起始位置
	 * @param preOed 先序遍历数组的终止位置
	 * @param midOst 中序遍历数组的起始位置
	 * @param midOed 中序遍历数组的终止位置
	 */
	public static void reBuild(TreeNode root,int preOst,int preOed,int midOst,int midOed) {
		//先序遍历的起始位置就是根节点
		root.value = preOrder[preOst];
		//找出根节点在中序遍历数组中的下标，下标小于它的就是它的左子树，大于它的是它的右子树
		int root_pos_at_midOrder = pos(root.value,midOrder);
		
		//表示左子树存在
		if(root_pos_at_midOrder - midOst > 0) {
			//为左子树分配空间
			root.left = new TreeNode();
			//为左子树指出范围，递归创建子树
			reBuild(root.left, preOst + 1, pos(midOrder[root_pos_at_midOrder-1],preOrder), midOst, root_pos_at_midOrder - 1);
		}
		//表示右子树存在
		if(midOed - root_pos_at_midOrder > 0) {
			//创建右子树
			root.right = new TreeNode();
			//为右子树指出范围，递归创建子树
			reBuild(root.right, pos(midOrder[root_pos_at_midOrder-1],preOrder) + 1,  preOed, root_pos_at_midOrder + 1, midOed);
		}
	}
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		TreeNode root = new TreeNode();
		reBuild(root, 0, preOrder.length-1, 0, midOrder.length-1);
		System.out.print(root);
	}

}