106.从中序与后序遍历序列构造二叉树 (Medium)*

题目描述*

根据一棵树的中序遍历与后序遍历构造二叉树。你可以假设树中没有重复的元素。

示例*

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

代码*

思想跟从先序和中序恢复差不多，从后序确定根结点。

递归

class Solution {
public:
    TreeNode *build(vector<int>& inorder, int start, int end, vector<int>& postorder, int rootPos, 
        unordered_map<int, int>& posMap) {
        if(start > end) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(postorder[rootPos]);
        int pos = posMap[postorder[rootPos]];
        root->right = build(inorder, pos + 1, end, postorder, rootPos - 1, posMap);
        root->left = build(inorder, start, pos - 1, postorder, rootPos - end + pos - 1, posMap);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0) {
            return nullptr;
        }
        unordered_map<int, int> posMap;
        for(int i = 0; i < inorder.size(); i++) {
            posMap[inorder[i]] = i;
        }
        return build(inorder, 0, inorder.size() - 1, postorder, postorder.size() - 1, posMap);
    }
};

最后更新: July 23, 2022