두 갈래 나무를 복원하다

1. 두 갈래 나무 복원

선순
뒷순서

2. 선순과 중순의 복원

----------------------------------------------
                            A
		             / \
			     B   C
			    / \  / \
			   D   E G  F           
----------------------------------------------

순차 반복 결과: ABDECGF
중간 순서 반복 결과: DBEAGCF
선순 중 각 나무의 노드 왼쪽 트리와 인접한 노드
오른쪽 트리 선착순 중 트리의 노드 거리 + 선착순 중 위치 다음은 오른쪽 트리
예를 들어 B 는 먼저 D [B] E 순서를 따릅니다.
B의 다음 노드는 왼쪽 나무에서 D가 찾을 수 있습니다.
오른쪽 나무 중서 B거리 1 그러면 오른쪽 나무는 선서 중 + 이 거리의 다음

/**
 *
 *    
 */
public class ConstructBinaryTree {

	public TreeNode buildTree(int[] preorder, int[] inorder) {
	       return findTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
			
			public TreeNode findTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inIndex,int inEnd){
				         if(preStart>=preorder.length||inIndex>inEnd)
				        	 return null;
				         
				         int i=inIndex;
				         
				         while(i<=inEnd){
				             if(preorder[preStart]==inorder[i++])
				            	 break;
				         }
				         
				         TreeNode tn=new TreeNode(preorder[preStart]);
				         
		                 tn.left=findTree(preorder,preStart+1,preEnd,inorder,inIndex,i-2);
		                 tn.right=findTree(preorder,preStart+i-inIndex,preEnd,inorder,i,inEnd);
				
				return tn;
			}
		
		public static void main(String[] args) {
			ConstructBinaryTree cbt=new ConstructBinaryTree();
			cbt.buildTree(new int[]{1,2,3}, new int[]{1,2,3});
		}
}

3. 후순과 선순의 환원

뒤따르기 결과: DEBGFCA
중간 순서 반복 결과: DBEAGCF
반대로. 오른쪽 나무가 왼쪽이야.
왼쪽 나무는 왼쪽부터+거리-1

/**
 *
 *    
 */
public class ConstructBinaryTreeTwo {

	public TreeNode buildTree(int[] inorder, int[] postorder) {
	       return findTree(postorder,postorder.length-1,0,inorder,0,inorder.length-1);
    }
			
	public TreeNode findTree(int[] postorder,int postEnd,int postStart,int[] inorder,int inIndex,int inEnd){
		   if(postEnd<postStart||inIndex>inEnd)
				   return null;
				         
		    int i=inIndex;
		    while(i<=inEnd){
				   if(postorder[postEnd]==inorder[i++])
				         break;
				 }
				         
	        TreeNode tn=new TreeNode(postorder[postEnd]);
		    tn.left=findTree(postorder,postStart+(i-inIndex-1),postStart,inorder,inIndex,i-2);
		    tn.right=findTree(postorder,postEnd-1,postStart+(i-inIndex-1),inorder,i,inEnd);
				
		    return tn;
}
		
		public static void main(String[] args) {
			ConstructBinaryTreeTwo cbt=new ConstructBinaryTreeTwo();
			cbt.buildTree(new int[]{1,3,2}, new int[]{3,2,1});
		}
}