此題為劍指offer的第7題 就是根據(jù)二叉樹的前序和中序遍歷的序列來構(gòu)造二叉樹并以層次遍歷的形式輸出。
考察了二叉樹的遍歷 稀拐。思想是前序遍歷的第一個值就是數(shù)的root節(jié)點(diǎn)实幕，然后去中序遍歷中找這個數(shù)，以此數(shù)為間隔鹦付，前面的為root的左子樹，后面的為root的右子樹择卦，然后之后就用同樣的方法分別構(gòu)建左右子樹敲长，所以可以使用遞歸來完成。 這里層次遍歷輸出方法是構(gòu)建一個隊列秉继，將根節(jié)點(diǎn)入隊祈噪，出隊的時候打印根節(jié)點(diǎn)，若此節(jié)點(diǎn)有左右子節(jié)點(diǎn)尚辑，則將左右子節(jié)點(diǎn)按順序入隊辑鲤，直到隊列為空時，所有節(jié)點(diǎn)都應(yīng)經(jīng)入隊并出隊杠茬。
實(shí)現(xiàn)代碼如下

import java.util.Arrays;
import java.util.LinkedList;

class TreeNode{
    TreeNode left,right;
    int value;
    public TreeNode(int value) {
        super();
        this.left = this.right =null;
        this.value = value;
    }   
}
public class Test7 {
    public static void main(String[] args) throws Exception{
        int[] foward = {1,2,4,7};
        int[] middle = {4,7,3,1};
        TreeNode newTree = getNewTree(foward,middle);
        printTree(newTree);
    }
    
    public static TreeNode getNewTree(int[] preorder,int[] inorder) throws Exception{
        if(preorder.length<=0 ||inorder.length<=0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);//preorder是前序遍歷的序列月褥，0位置上是根節(jié)點(diǎn)
        int index =  getindex(inorder, preorder[0]);//inorder中根節(jié)點(diǎn)的位置，前面的為左子樹瓢喉，后邊的為右子樹
        if(index==-1){
            throw new Exception("序列不匹配");
        }
        if(preorder.length==1){
            return root;
        }
        int[] left = Arrays.copyOfRange(inorder, 0, index);
        int[] right = Arrays.copyOfRange(inorder, index+1, inorder.length);
        
        int[] newpreleft = Arrays.copyOfRange(preorder, 1, index+1);
        int[] newpreright = Arrays.copyOfRange(preorder, preorder.length-index-1, preorder.length);
        
        if(left.length>0){
            root.left = getNewTree(newpreleft,left);    
        }
        if(right.length>0){
            root.right = getNewTree(newpreright, right);
        }
        return root;
    }
    public static int getindex(int arr[],int number){

        for(int i=0;i<arr.length;i++){
            if(arr[i]==number){
                return i;
            }
        }
        return -1;
    }
    public static void printTree(TreeNode root){
        {
              if(root == null)
              {
                  return ;
              }
              LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
              TreeNode current = null;
              queue.offer(root);//將根節(jié)點(diǎn)入隊
              while(!queue.isEmpty())
              {
                  current = queue.poll();//出隊隊頭元素并訪問
                  System.out.print(current.value +"-->");
                  if(current.left != null)//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)不為空入隊
                  {
                      queue.offer(current.left);
                  }
                  if(current.right != null)//如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)不為空宁赤，把右節(jié)點(diǎn)入隊
                  {
                      queue.offer(current.right);
                  }
              }
              
        }
    }

}