題目：

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

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

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

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

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

? 按此思路我們用遞歸實現時，應該先遞歸創建右子樹，在遞歸創建左子樹。

代碼如下：

class Solution {
    int pos_index;
    int[] postorder;

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


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        
        int index = 0;
        //將inorder數組中的元素存放到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時，說明分割的子數組中沒有節點來構造樹了
        if(left >right){
            return null;
        }
        //獲取后序遍歷序列的最后一個元素，并為根節點
        
        int value = postorder[pos_index];
    
        //將pos_index左移
        pos_index--;
        //封裝為根節點
        TreeNode root = new TreeNode(value);
        
        //找到value在中序遍歷序列的索引
        int index = inorder_map.get(value);
        

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

        return root;
    



    }
    
}

總結：主要是利用后序遍歷序列來確定根節點，在以此根節點到中序遍歷序列中來確定改根節點的左右子樹，通過參數left和right來動態變化創建子樹的左右邊界。

后序遍歷實現：

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

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

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