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

本文针对原链接题解的比较晦涩的地方重新进行说明解释
原题解链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solutions/50561/tu-jie-gou-zao-er-cha-shu-wei-wan-dai-xu-by-user72

1.解题关键

后序遍历序列的最后一个元素一定是root节点，中序遍历序列里面，root左边的是左子树，root节点右边的是右子树，接着可以递归处理。
依次把数组分为

2.思路

先使用哈希表记录整个中序序列的数组元素与下标的关系，目的是为了后续直接获取后序遍历序列vector最后一个元素之后直接得到中序里面的root节点的下标，加快算法速度！

3.变量名缩写与英文单词对应关系

变量名缩写	变量名单词
is	inorder_start（中序遍历数组-起始下标）
ie	inorder_end（中序遍历数组-末尾下标）
ps	poster_start（后序遍历数组-起始下标）
pe	poster_end（后序遍历数组-末尾下标）
ri	root_index(根节点的下标)

4.算法思路图解

5.代码

class Solution {
public:
    unordered_map<int,int> map;
    vector<int>* post;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {        
        for(int i=0;i<inorder.size();++i){
            map[inorder[i]]=i;
        }
        post=&postorder;
        TreeNode* root=dfs(0,inorder.size()-1,0,post->size()-1);
        return root;
    }
    TreeNode* dfs(int is,int ie,int ps,int pe){
        if(ie<is||pe<ps){
            return nullptr;
        }
        int root = (*post)[pe];
        int ri=map[root];
        TreeNode* node=new TreeNode(root);
        node->left=dfs(is,ri-1,ps,ri-is-1+ps);
        node->right=dfs(ri+1,ie,ri-is+ps,pe-1);
        return node;
    }
};

原文地址：https://blog.csdn.net/weixin_46028606/article/details/136804694

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！