日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

題目：

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

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

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

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

我們用變量pos_index來從后往前遍歷postorder數(shù)組（后序遍歷序列），初始值為pos_index = postorder.length - 1，因為后序遍歷是 左 --->右 --->根 順序遍歷，所以當我們從后往前遍歷postorder數(shù)組時，先訪問的是右子樹的節(jié)點。

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

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

代碼如下：

class Solution {
    int pos_index;
    int[] postorder;

    //創(chuàng)建map，來存放中序序列的值和對應的索引值
    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){
        //當left >right時，說明分割的子數(shù)組中沒有節(jié)點來構(gòu)造樹了
        if(left >right){
            return null;
        }
        //獲取后序遍歷序列的最后一個元素，并為根節(jié)點
        
        int value = postorder[pos_index];
    
        //將pos_index左移
        pos_index--;
        //封裝為根節(jié)點
        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é)點，在以此根節(jié)點到中序遍歷序列中來確定改根節(jié)點的左右子樹，通過參數(shù)left和right來動態(tài)變化創(chuàng)建子樹的左右邊界。

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

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

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

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

新聞名稱：leetcode106.從中序與后序遍歷序列構(gòu)造二叉樹-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://www.dlmjj.cn/article/dcejjc.html