72. Construct Binary Tree from Inorder and Postorder Traversal

class Solution { public: /** * @param inorder: A list of integers that inorder traversal of a tree * @param postorder: A list of integers that postorder traversal of a tree * @return: Root of a tree */ unordered_map<int, int> mp; TreeNode * buildTree(vector<int> &inorder, vector<int> &postorder) { // write your code here //这里是inorder和postorder，和inorder 和 preorder 类似吧。 // 左根右，左右根 const int sizeI = inorder.size(); const int sizeP = postorder.size(); if(sizeI == 0){ return NULL; } if(sizeP != sizeI){ return NULL; } for(int i = 0; i < sizeI; i++){ mp[inorder[i]] = i; } return hepler(inorder, postorder, 0, sizeI - 1, 0, sizeP - 1); } TreeNode *hepler(vector<int> &inorder, vector<int> &postorder, int startI, int endI, int startP, int endP){ if(startI > endI || startP > endP){ return NULL; } int rootIdx = mp[postorder[endP]]; int leftNum = rootIdx - startI; TreeNode *left = hepler(inorder, postorder, startI, rootIdx - 1, startP, startP + leftNum - 1); TreeNode *right = hepler(inorder, postorder, rootIdx + 1, endI, startP + leftNum, endP - 1); TreeNode *root = new TreeNode(inorder[rootIdx]); root->left = left; root->right = right; return root; } };