검지 Offer_두 갈래 나무 재건_04

package test;

import java.util.LinkedList;

public class Test
{
	public static void main(String[] args)
	{
		int[] preOrder = {1,2,4,8,9,5,3,6,7};// 
		int[] midOrder = {8,4,9,2,5,1,6,3,7};// 
		TreeNode biTree = reConstructBiTree(preOrder,midOrder);// 
		levelOrder(biTree);// 
	}
	
	public static TreeNode reConstructBiTree(int[] preOrder, int[] midOrder)
	{
		TreeNode root = reBiTree(preOrder,0,preOrder.length-1, midOrder,0,midOrder.length-1);
		return root;
	}
	
	public static TreeNode reBiTree(int[] pre, int preL, int preR, int[] mid, int midL, int midR)
	{// 、 。
		if(preL > preR || midL > midR)
			return null;
		
		TreeNode now = new TreeNode(pre[preL]);
		for(int i = midL; i <= midR; i++)
		{
			if(mid[i] == pre[preL])
			{
				now.left = reBiTree(pre,preL+1,i-midL+preL, mid,midL,i-1);
				now.right = reBiTree(pre,i-midL+preL+1,preR, mid,i+1,midR);
			}
		}
		
		 return now;
	}
	
	public static void levelOrder(TreeNode biTree)
	{// 
		if(biTree == null)
			return;
		LinkedList list = new LinkedList();
		list.add(biTree);
		TreeNode now;
		while(!list.isEmpty())
		{
			now = list.poll();
			System.out.println(now.value);
			if(now.left != null)
				list.add(now.left);
			if(now.right != null)
				list.add(now.right);
		}
	}
}

class TreeNode// 
{
	int value;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int value)
	{
		this.value = value;
	}
}