[LeetCode]109. Construct Binary Tree from Inorder and Postorder Traversal由中序序列和后序序列重建二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int in = inorder.size(), pn = postorder.size();
        if (in == 0 || pn == 0 || in != pn) return NULL;
        return buildRecursion(inorder, 0, in - 1, postorder, 0, pn - 1);
    }
private:
    TreeNode* buildRecursion(vector<int>& inorder, int ibeg, int iend, vector<int>& postorder, int pbeg, int pend) {
        TreeNode *root = new TreeNode(postorder[pend]);
        if (ibeg == iend) return root;
        int rootIndex = ibeg;
        while (rootIndex <= iend && inorder[rootIndex] != root->val) 
            ++rootIndex;
        int leftLength = rootIndex - ibeg, rightLength = iend - rootIndex;
        if (leftLength > 0) 
            root->left = buildRecursion(inorder, ibeg, rootIndex - 1, postorder, pbeg, pbeg + leftLength - 1);
        if (rightLength > 0) 
            root->right = buildRecursion(inorder, rootIndex + 1, iend, postorder, pend - rightLength, pend - 1);
        return root;
    }
};