? ? ? ?給定兩個整數(shù)數(shù)組?preorder?和?inorder?，其中?preorder?是二叉樹的先序遍歷，?inorder?是同一棵樹的中序遍歷，請構(gòu)造二叉樹并返回其根節(jié)點。

? ? ? ?題目中是給定兩個數(shù)組，一個是存放這顆樹的前序遍歷的數(shù)組，一個是存放這棵樹的中序遍歷的數(shù)組，解這道題的關(guān)鍵我們首先要知道樹的前中序遍歷分別指的是什么？它們兩者之間到底存在著什么關(guān)系？解下來讓我們一探究竟

前序遍歷：

? ? ? ?前序遍歷的遍歷順序是中左右，先遍歷自己，后遍歷自己的左子樹，最后再遍歷自己的右子樹，由上圖已知該樹的前序遍歷為[3，9，20，15，7]

中序遍歷：

? ? ? ?中序遍歷的遍歷順序是左中右，先遍歷左子樹，后遍歷自己，最后再遍歷自己的右子樹，由上圖已知該樹的中序遍歷為[9，3，15，20，7]

?觀看這兩個數(shù)組，有沒有發(fā)現(xiàn)什么特別的地方？

? ? ? ?樹是一種天然的遞歸結(jié)構(gòu)，每棵子樹也可以稱為一棵獨立的樹，根據(jù)上圖我們不難發(fā)現(xiàn)，數(shù)組中的元素是嚴(yán)格按照中左右的順序填充的

?

?根據(jù)上圖我們不難發(fā)現(xiàn)，數(shù)組中的元素是嚴(yán)格按照中左右的順序填充的

所以我們再來看這兩個數(shù)組的特點：

?我們已經(jīng)得知了這兩個數(shù)組中的相存的特點，接下來就可以擼代碼了

• 我們要通過數(shù)組中的元素值得到該元素在數(shù)組中的索引為位置，所們先要使用Map結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)去對我們的中序遍歷時的數(shù)據(jù)進行預(yù)處理

 Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}

• 然后開始我們的構(gòu)建函數(shù)dfs（前序數(shù)組，前序開始的位置，前序結(jié)束的位置，中序數(shù)組，中序開始的位置，中序結(jié)束的位置）

 return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);

• 遞歸時如果出先了開始位置比結(jié)束位置還要大的時候，這種情況肯定是不滿足我們的條件的，所以直接拋出null就可以了

if(pStart>pEnd||iStart>iEnd){return null;}

• 通過前序遍歷數(shù)組拿到我們相對根節(jié)點，然后通過map去查詢我們中序數(shù)組中我們的相對根節(jié)點的索引index，因為我們的中序遍歷是左中右，所以中序遍歷中的index-iStart的長度就是我們相對子樹的節(jié)點的個數(shù)

 int val=preorder[pStart];TreeNode root=new TreeNode(val);int size=map.get(val);int length=size-iStart;

• 最后開始dfs，構(gòu)造左右子樹，這道題就完成了

    //     不包括當(dāng)前的根結(jié)點   前序取不到起點（左開右閉）   中序取不到終點（左閉右開）root.left=dfs(preorder,pStart+1,pStart+length,inorder,iStart,size-1);//                  左子樹下一次遞歸的起點 root.right=dfs(preorder,pStart+length+1,pEnd,inorder,size+1,iEnd);//                  右子樹下一次遞歸的起點

接下來上源碼供大家參考：

  Map<Integer,Integer> map=new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder==null||inorder==null){return null;}for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode dfs(int[] preorder,int pStart,int pEnd,int[]inorder,int iStart,int iEnd){if(pStart>pEnd||iStart>iEnd){return null;}int val=preorder[pStart];TreeNode root=new TreeNode(val);int size=map.get(val);int length=size-iStart;root.left=dfs(preorder,pStart+1,pStart+length,inorder,iStart,size-1);root.right=dfs(preorder,pStart+length+1,pEnd,inorder,size+1,iEnd);return root;}