leetcode106.从中序与后序遍历序列构造二叉树-创新互联

题目：

中序遍历特点：先遍历左子树，再遍历根节点，最后遍历右子树

后序遍历特点：先遍历左子树，再遍历右子树，最后遍历根节点

根据后序遍历的特点，我们可以得到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元起，快前往官网查看详情吧