Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
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 *buildTree(unordered_map<int, int> &map, vector<int> &preorder,int ps, int pe, vector<int> &inorder, int is, int ie) { if(ps>pe) return NULL; int i= map[preorder[ps]]; TreeNode *node = new TreeNode(inorder[i]); node->left = buildTree(map,preorder, ps+1, ps+i-is, inorder, is, i-1); node->right = buildTree(map,preorder, ps+i-is+1, pe, inorder, i+1, ie); return node; } TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { unordered_map<int, int> map; for(int i=0;i<inorder.size();i++) { map[inorder[i]] = i; } int len = preorder.size(); return buildTree(map, preorder, 0, len-1, inorder, 0, len-1); } };