package cn.pbdata.util;

public class PreMidToAfter {

    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(){
            left = null;
            right = null;
        }
    }
    
    public TreeNode rebuild(int[] pre,int[] mid){
        return rebuild(pre,0,pre.length-1,mid,0,mid.length-1);
    }
    
    public TreeNode rebuild(int[] pre,int ps,int pe,int[] mid,int ms,int me){
        if(pre == null || pre.length == 0 || mid == null || mid.length==0){
            return null;
        }
        if(ps > pe){
            return null;
        }
        int val = pre[ps];
        TreeNode root = new TreeNode();
        root.val = val;
        
        int index;
        for(index = ms ; index <= me;index++){
            if(val == mid[index]){
                break;
            }
        }
        
        int leftPreStart = ps + 1;
        int leftPreEnd = ps + index - ms;
        int leftMidStart = ms;
        int leftMidEnd = index - 1;
        
        root.left = rebuild(pre,leftPreStart,leftPreEnd,mid,leftMidStart,leftMidEnd);
        
        int rightPreStart = ps + index -ms + 1;
        int rightPreEnd  = pe;
        int rightMidStart = index + 1;
        int rightMidEnd = me;
        root.right = rebuild(pre,rightPreStart,rightPreEnd,mid,rightMidStart,rightMidEnd);
        return root;
    }
    public void preView(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val);
        preView(root.left);
        preView(root.right);
    }
    public void midView(TreeNode root){
        if(root == null){
            return;
        }
        midView(root.left);
        System.out.print(root.val);
        midView(root.right);
    }
    public void lastView(TreeNode root){
        if(root == null){
            return;
        }
        lastView(root.left);
        lastView(root.right);
        System.out.print(root.val);
    }
    
    
    public static void main(String[] args){
        PreMidToAfter pt = new PreMidToAfter();
        int[] pre = { 1, 2, 4,7,3,5,6,8};
        int[] mid = {4,7,2,1,5,3,8,6};
        TreeNode node1 = pt.rebuild(pre, mid);
        pt.preView(node1); 
        System.out.println("");
        pt.midView(node1);
        System.out.println("");
        pt.lastView(node1);
        System.out.println("");
        
    }
}