73. Construct Binary Tree from Preorder and Inorder 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> &preorder, vector<int> &inorder) { // write your code here // preorder: 根左右 // inorder: 左根右 // 根据preoder中的根，找到inorder中position, then the left side is the left substree, the right side is the right substree // recursion TreeNode *res; int sizeN = preorder.size(); if(sizeN == 0){ return NULL; } for(int i = 0; i < sizeN; i++){ mp[inorder[i]] = i; } return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1); } TreeNode *build(vector<int> &preorder, int startP, int endP, vector<int> &inorder, int startI, int endI){ if(startI > endI || startP > endP){ return NULL; //这里忽略了 } int rootInx = mp[preorder[startP]]; TreeNode *root = new TreeNode(inorder[rootInx]); int num = rootInx - startI; TreeNode *left = build(preorder, startP + 1, startP + num, inorder, startI, rootInx -1); TreeNode *right = build(preorder, startP + num + 1, endP, inorder, rootInx + 1, endI); root->left = left; root->right = right; return root; } };