資料結構與算法分析筆記與總結(java實作)--二叉樹24：重建二叉樹

題目：輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。

思路：已知一棵樹的先序周遊的結果數組和中序周遊的結果，要求據此重建一棵二叉樹，即重建所有結點并設定結點之間的指針關系，最後傳回這棵樹的根結點。分析二叉樹的前序周遊和中序周遊的特征。

先序周遊：①[②④⑦][③⑤⑥⑧]

中序周遊：[④⑦②]①[⑤③⑧⑥]

對于先序周遊的數組arr1[begin,end]，第一個元素就是數組對應樹的根結點，顯然①是根結點，然後根據值1周遊中序數組arr2,已知元素不重複，是以可以找到唯一的元素，找到其在arr2中的位置為i，此時arr2中[begin,i-1]是結點①的左子樹對應的數組，[i+1,end]是結點①的右子樹對應的數組，分别求出這2個子數組的長度length1=i-1-begin+1=i-begin；length2=end-i-1+1=end-i。然後取先序數組arr1中找出對應的子數組,分别是[begin+1,begin+length1]，[begin+lenght1+1,end]，于是得到了:

用來建構結點①左子樹所需的先序數組和中序數組arr1[begin+1,begin+length1]+arr2[begin,i-1];

用來建構結點①右子樹所需的先序數組和中序數組arr2[begin+lenght1+1,end]+arr2[i+1,end];

于是問題有回到了原始的問題上面來了，調用遞歸方法分别出入這2個數組以及邊界，傳回建立起來的二叉樹的頭結點，然後将其與目前結點arr1[begin]連接配接起來即可。

邊界條件是：如果數組對于arr1數組或者arr2數組，有begin<end，那麼說明此時對應的樹為null，直接傳回null即可。

F⑤：tempNode是方法體内部的局部變量，隻在本方法中有效，于是當遞歸傳回到上一層後目前的tempNode就失效了，是以不能直接在上一層的方法中通路tempNode來擷取之前的tempNode,但是使用傳回是正确的，每次tempNode隻需要在本層方法中起作用，所得結果會傳回給上一層的方法，傳回之前會為其關聯上子樹對象，于是傳回的結點總是帶着子樹的，越往上傳回子樹越大，直到最後傳回的是一棵完整的二叉樹，是以這裡不需要講tempNode設定成為全局或者成員變量。

//輸入二叉樹的先序和中序數組，重建二叉樹傳回樹的頭結點

publicclass Solution {

    public TreeNode reConstructBinaryTree(int[] pre,int [] in) {

       //特殊輸入

       if(pre.length!=in.length||pre.length<=0)return null;

       //調用遞歸函數解決問題并傳回頭結點

        returnthis.process(pre,0,pre.length-1,in,0,in.length-1);

    }

   //遞歸函數：傳入二叉樹的先序和中序周遊的數組或者數組區間，傳回建構的二叉樹的頭結點

    private TreeNode process(int[] arr1,intbegin1,int end1,int[] arr2,int begin2,int end2){

       //關鍵：邊界條件，如果begin=end最終也會變成begin>end

        if(begin1>end1||begin2>end2)return null;

       //①先找根結點

        int val=arr1[begin1];

       //②找到val在中序數組arr2中的位置i

        int i=this.getIndexInArr2(arr2,val);

       //③求出中序數組中2個區間的長度

        int length1=i-begin2;

        int length2=end2-i;

       //④找出先序數組中對應的數組

        TreeNodeleftNode=this.process(arr1,begin1+1,begin1+length1,arr2,begin2,i-1);

        TreeNode rightNode=this.process(arr1,begin1+length1+1,end1,arr2,i+1,end2);

       //F⑤建立目前結點并将其與左右結點連接配接

        TreeNodetempRoot=new TreeNode(val);

        tempRoot.left=leftNode;

        tempRoot.right=rightNode;

       //傳回建立二叉樹的根結點

        return tempRoot;

    }

   //函數：根據值val在數組中找到對應的下标

    private int getIndexInArr2(int[] arr,intval){

        int res=0;

        for(int i=0;i<arr.length;i++){

            if(arr[i]==val) res=i;

        }

        return res;

    }

}