106. Construct Binary Tree from

题目链接

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

代码

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return dfs(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);

    }

    TreeNode* dfs(vector<int>& inorder, int is, int ie, vector<int>& postorder, int ps, int pe) {
        if (is > ie) {
            return NULL;
        }
        int val = postorder[pe];
        TreeNode *parent = new TreeNode(val);
        int ii = is, pi = ps;
        while (ii <= ie && val != inorder[ii]) {
            ii++;
            pi++;
        }
        parent->left = dfs(inorder, is, ii - 1, postorder, ps, pi - 1);
        parent->right = dfs(inorder, ii + 1, ie, postorder, pi, pe - 1);
        return parent;
    }
};