本文主要是介绍106. 从中序与后序遍历序列构造二叉树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：

后序遍历：

[[左子树的前序遍历结果]，[右子树的前序遍历结果]，根节点]

中序遍历：

[[左子树的前序遍历结果]，根节点，[右子树的前序遍历结果]]

从后往前遍历后序遍历序列，首先拿到整棵树的根节点的值
带着该值去中序遍历序列中找到该值的定位，将中序遍历分为左右两部分
得出左右两部分的长度之后，就可以在后序遍历序列中找到左子树的根节点和右子树的根节点，重复上述步骤

注意：

比较麻烦的是区间的更新

函数：

buildMyTree(
int[] inorder 中序遍历序列
,int[] postorder 后序遍历序列
,int inorder_left 当前树在中序遍历序列的左区间
,int inorder_right 当前树在中序遍历序列的左区间
,int postorder_left 当前树在中序遍历序列的左区间
,int postorder_right 当前树在中序遍历序列的左区间
)

1. 在后序遍历序列中获得根节点的值
2. 获得根节点在中序遍历序列中的定位
3. 构建根节点
4. 递归地遍历左子树，将左子树的根节点赋给根节点的左子节点
5. 递归地遍历右子树，将右子树的根节点赋给根节点的右子节点
6. 返回根节点

代码

class Solution {
    Map<Integer,Integer> map=new HashMap<>();
    public TreeNode buildMyTree(int[] inorder,int[] postorder,int inorder_left,int inorder_right,int postorder_left ,int postorder_right)
    {
        if(postorder_left>postorder_right)
        {
            return null;
        }
         int post=postorder[postorder_right];
         int in=map.get(post);
         //System.out.println(post+" "+in);
         int leftlen=in-1-inorder_left+1;
         int rightlen=inorder_right-(in+1)+1;
         TreeNode head=new TreeNode(post);
         head.left=buildMyTree(inorder,postorder,inorder_left,in-1,postorder_left,postorder_left+leftlen-1);
         head.right=buildMyTree(inorder,postorder,in+1,inorder_right,postorder_left+leftlen,postorder_right-1);
         return head;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) 
    {
        int n=inorder.length;
         for(int i=0;i<n;i++)
         {
             map.put(inorder[i],i);
         }
         return buildMyTree(inorder,postorder,0,n-1,0,n-1);
    }
}

这篇关于106. 从中序与后序遍历序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！