[LeetCode]Construct Binary Tree from Inorder and Postorder Traversal

[cpp]
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
//Note:
//You may assume that duplicates do not exist in the tree.
//so we can build an unordered_map O(1) to look up the index in inorder, to divide the left subtree and right subtree
//in postorder.
//inorder{(inStart)left(inRootIdx-1)root(inRootIdx+1)right}, postorder{left(inRootIdx-1)right(PostEnd-1)root}
public:
unordered_map m_Value2Index;//inorder map
void BuildMap(vector &inorder)
{
m_Value2Index.clear();
for(int i = 0; i < inorder.size(); ++i)
m_Value2Index[inorder[i]] = i;
}
TreeNode* BuildTreeInPlusPost(vector &inorder, int inLow, int inHigh, vector &postorder, int postLow, int postHigh )
{
if(inLow > inHigh || postLow > postHigh)
return NULL;
int rootValue = postorder[postHigh];
TreeNode* parent = new TreeNode(rootValue);
int inRootIdx = m_Value2Index[rootValue];
parent->left = BuildTreeInPlusPost(inorder, inLow, inRootIdx-1, postorder, postLow, postLow+inRootIdx-inLow-1);
parent->right = BuildTreeInPlusPost(inorder, inRootIdx+1, inHigh, postorder, postLow+inRootIdx-inLow, postHigh-1);
return parent;
}
TreeNode *buildTree(vector &inorder, vector &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
BuildMap(inorder);
return BuildTreeInPlusPost(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
}

};

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
//Note:
//You may assume that duplicates do not exist in the tree.
//so we can build an unordered_map O(1) to look up the index in inorder, to divide the left subtree and right subtree
//in postorder.
//inorder{(inStart)left(inRootIdx-1)root(inRootIdx+1)right}, postorder{left(inRootIdx-1)right(PostEnd-1)root}
public:
unordered_map m_Value2Index;//inorder map
void BuildMap(vector &inorder)
{
m_Value2Index.clear();
for(int i = 0; i < inorder.size(); ++i)
m_Value2Index[inorder[i]] = i;
}
TreeNode* BuildTreeInPlusPost(vector &inorder, int inLow, int inHigh, vector &postorder, int postLow, int postHigh )
{
if(inLow > inHigh || postLow > postHigh)
return NULL;
int rootValue = postorder[postHigh];
TreeNode* parent = new TreeNode(rootValue);
int inRootIdx = m_Value2Index[rootValue];
parent->left = BuildTreeInPlusPost(inorder, inLow, inRootIdx-1, postorder, postLow, postLow+inRootIdx-inLow-1);
parent->right = BuildTreeInPlusPost(inorder, inRootIdx+1, inHigh, postorder, postLow+inRootIdx-inLow, postHigh-1);
return parent;
}
TreeNode *buildTree(vector &inorder, vector &postorder) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
BuildMap(inorder);
return BuildTreeInPlusPost(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1);
}

};