LeetCode[Tree]: Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

這個題目的解法與LeetCode[Tree]: Construct Binary Tree from Preorder and Inorder Traversal的解法幾乎相差無幾。我的C++代碼實作如下：

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        return buildTreeHelper(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
    }

    TreeNode *buildTreeHelper(vector<int> ::iterator inBegin, vector<int> ::iterator inEnd, vector<int> ::iterator postBegin, vector<int> ::iterator postEnd) {
        if (postEnd <= postBegin) return nullptr;

        TreeNode *root = new TreeNode(*(postEnd - 1));
        int leftNodes  = find(inBegin, inEnd, *(postEnd - 1)) - inBegin;
        root->left  = buildTreeHelper(inBegin, inBegin + leftNodes, postBegin, postBegin + leftNodes);
        root->right = buildTreeHelper(inBegin + leftNodes + 1, inEnd, postBegin + leftNodes, postEnd - 1);

        return root;
    }
};
           

時間性能如下圖所示：