題目：

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括花山網(wǎng)站建設(shè)、花山網(wǎng)站制作、花山網(wǎng)頁制作以及花山網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，花山網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到花山省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

中序遍歷特點(diǎn)：先遍歷左子樹，再遍歷根節(jié)點(diǎn)，最后遍歷右子樹

后序遍歷特點(diǎn)：先遍歷左子樹，再遍歷右子樹，最后遍歷根節(jié)點(diǎn)

根據(jù)后序遍歷的特點(diǎn)，我們可以得到postorder數(shù)組最后一個(gè)元素就是根節(jié)點(diǎn)，root?= 3，在中序遍歷中找到該節(jié)點(diǎn)，根據(jù)中序遍歷的特點(diǎn)就可以找到根節(jié)點(diǎn)的左右子樹，[9]就是左子樹的所有值，[15 , 20 , 7]就是右子樹的所有的值。

我們用變量pos_index來從后往前遍歷postorder數(shù)組（后序遍歷序列），初始值為pos_index = postorder.length - 1，因?yàn)楹笮虮闅v是 左 --->右 --->根 順序遍歷，所以當(dāng)我們從后往前遍歷postorder數(shù)組時(shí)，先訪問的是右子樹的節(jié)點(diǎn)。

定義遞歸函數(shù) buildTree(left, right)表示當(dāng)前遞歸到中序序列中當(dāng)前子樹的左右邊界，遞歸入口為buildTree(0, n - 1);

? 按此思路我們用遞歸實(shí)現(xiàn)時(shí)，應(yīng)該先遞歸創(chuàng)建右子樹，在遞歸創(chuàng)建左子樹。

代碼如下：

class Solution {
    int pos_index;
    int[] postorder;

    //創(chuàng)建map，來存放中序序列的值和對應(yīng)的索引值
    HashMapinorder_map = new HashMap();


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        
        int index = 0;
        //將inorder數(shù)組中的元素存放到inorder_map中，方便后面找索引位置
        for(Integer value : inorder){
            inorder_map.put(value,index++);
        }
        pos_index = postorder.length - 1;
    return buildTree(0,pos_index);
        

    }
    public TreeNode buildTree(int left,int right){
        //當(dāng)left >right時(shí)，說明分割的子數(shù)組中沒有節(jié)點(diǎn)來構(gòu)造樹了
        if(left >right){
            return null;
        }
        //獲取后序遍歷序列的最后一個(gè)元素，并為根節(jié)點(diǎn)
        
        int value = postorder[pos_index];
    
        //將pos_index左移
        pos_index--;
        //封裝為根節(jié)點(diǎn)
        TreeNode root = new TreeNode(value);
        
        //找到value在中序遍歷序列的索引
        int index = inorder_map.get(value);
        

        //遞歸創(chuàng)建右子樹
        root.right = buildTree(index + 1, right);
        //遞歸創(chuàng)建左子樹
        root.left = buildTree(left,index - 1);

        return root;
    



    }
    
}

總結(jié)：主要是利用后序遍歷序列來確定根節(jié)點(diǎn)，在以此根節(jié)點(diǎn)到中序遍歷序列中來確定改根節(jié)點(diǎn)的左右子樹，通過參數(shù)left和right來動(dòng)態(tài)變化創(chuàng)建子樹的左右邊界。

后序遍歷實(shí)現(xiàn)：

public void postorder(TreeNode root){
    if(root == null){
        return null;    
    }
    //遞歸左子樹
    postorder(root.left);
    //遞歸右子樹
    postorder(root.right);
    
    //打印根節(jié)點(diǎn)
    System.out.print(root.val);
    
}

我們通過上述代碼得到了后序遍歷序列，現(xiàn)在要反向遍歷后序序列（因?yàn)楦鶕?jù)后序遍歷特點(diǎn)，根在序列末尾）將其還原成樹，就需要將上述代碼的遍歷過程反向即可（也就是反向的前序遍歷 根 ---- 右 --- 左），這也就是為什么要先創(chuàng)建右子樹，再創(chuàng)建左子樹。利用后序序列我們只能知道根，而不能確定當(dāng)前根的左右子樹的范圍，這時(shí)候我們就需要借助中序遍歷來確定根的子樹的邊界。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：leetcode106.從中序與后序遍歷序列構(gòu)造二叉樹-創(chuàng)新互聯(lián)
瀏覽路徑：http://www.rwnh.cn/article22/dcejjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、網(wǎng)站內(nèi)鏈、ChatGPT、做網(wǎng)站、企業(yè)網(wǎng)站制作、服務(wù)器托管

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)