106. 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

文章目录

题目描述：示例:方法

C++Java 通过截图

---

题目描述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

示例:

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

方法 C++

class Solution {
private:
    // unordered_mapmap;
    TreeNode* buildTree(vector& inorder,int iStart,int iEnd,vector& postorder,int pStart,int pEnd){
        if(iStart>iEnd)
            return nullptr;
        int rootVal=postorder[pEnd];
        int rootIdx=-1;
        for(int i=iStart;i<=iEnd;i++){
            if(inorder[i]==rootVal){
                rootIdx=i;
                break;
            }
        }
        int leftLen=rootIdx-iStart;
        TreeNode* root=new TreeNode(rootVal);
        root->left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1);
        root->right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1);
        return root;
    }

public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        return buildTree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }
};

用unordered_mapmap;
int rootIdx=map[rootVal];得到rootVal的索引

class Solution {
private:
    unordered_mapmap;
    TreeNode* buildTree(vector& inorder,int iStart,int iEnd,vector& postorder,int pStart,int pEnd){
        if(iStart>iEnd)
            return nullptr;
        int rootVal=postorder[pEnd];
        int rootIdx=map[rootVal];
        int leftLen=rootIdx-iStart;
        TreeNode* root=new TreeNode(rootVal);
        root->left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1);
        root->right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1);
        return root;
    }

public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        for(int i=0;i 
Java 
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }

    TreeNode buildTree(int[] inorder,int iStart,int iEnd,int[] postorder,int pStart,int pEnd){
        if(iStart>iEnd)
            return null;
        int rootVal=postorder[pEnd];
        int rootIdx=-1;
        for(int i=iStart;i<=iEnd;i++){
            if(inorder[i]==rootVal){
                rootIdx=i;
                break;
            }
        }
        int leftLen=rootIdx-iStart;
        TreeNode root=new TreeNode(rootVal);
        root.left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1);
        root.right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1);
        return root;
    }
}
 
用Mapidx_map=new HashMap<>();
 int rootIdx=idx_map.get(rootVal);得到rootVal的索引
 
class Solution {
    Mapidx_map=new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0;iiEnd)
            return null;
        int rootVal=postorder[pEnd];
        int rootIdx=idx_map.get(rootVal);
        int leftLen=rootIdx-iStart;
        TreeNode root=new TreeNode(rootVal);
        root.left=buildTree(inorder,iStart,rootIdx-1,postorder,pStart,pStart+leftLen-1);
        root.right=buildTree(inorder,rootIdx+1,iEnd,postorder,pStart+leftLen,pEnd-1);
        return root;
    }
}
 
通过截图 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5716109.html