Construct_Binary_Tree_from_Inorder_and_Postorder_Traversal.txt

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

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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTreeHelper(vector<int> &inorder,int li, int ri,vector<int> &postorder, int lp, int rp){
        if (li>ri || lp>rp) return NULL;
        int rootvalue = postorder[rp];
        TreeNode *node = new TreeNode(rootvalue);
        int leftsize, rightsize;
        for (int i=li; i<=ri; ++i){
            if (rootvalue==inorder[i]){
                leftsize = i-li;
                rightsize = ri-i;
                break;
            }
        }
        node->left = buildTreeHelper(inorder,li,li+leftsize-1,postorder,lp,lp+leftsize-1);
        node->right = buildTreeHelper(inorder,ri-rightsize+1,ri,postorder,rp-rightsize,rp-1);
        return node;
    }

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return buildTreeHelper(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
    }
};

1.IDEA and Note please refer to the file: "Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.txt"