Given inorder and postorder 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 a binary tree node. * 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> &postorder,int ps, int pe, vector<int> &inorder, int is, int ie) { if(ps>pe) return NULL; int i= map[postorder[pe]]; TreeNode *node = new TreeNode(postorder[pe]); node->left = buildTree(map,postorder, ps, ps+i-is-1, inorder, is, i-1); node->right = buildTree(map,postorder, ps+i-is, pe-1, inorder, i+1, ie); return node; } TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { unordered_map<int, int> map; for(int i=0;i<inorder.size();i++) { map[inorder[i]] = i; } int len = postorder.size(); return buildTree(map, postorder, 0, len-1, inorder, 0, len-1); } };