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

两天宇宙人

2020-02-20

😂递归

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return helper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
    TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int ib, int ie, int pb, int pe)
    {
        if(ib > ie) 
            return nullptr;
        int top = postorder[pe];
        int pmid = -1;
        for(int i = ib; i <= ie; ++i) {
            if(inorder[i] == top) 
                pmid = i;
        }
        TreeNode* new_one = new TreeNode(top);
        new_one->right = helper(inorder, postorder,pmid + 1, ie, pb, pe - 1);
        new_one->left = helper(inorder, postorder,ib, pmid - 1, pb, pe - 1 + pmid - ie);
        return new_one;
    }
};