Note:
You may assume that duplicates do not exist in the tree.
Solution: the same idea as the solution to Construct Binary Tree from Inorder and Postorder Traversal.
/** * 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(vector<int> &preorder, vector<int> &inorder) { // Note: The Solution object is instantiated only once and is reused by each test case. if(inorder.size()!=preorder.size() || inorder.size()==0) return NULL; int curVal = preorder[0]; int i=0; while(i<inorder.size()){ if(inorder[i]==curVal) break; ++i; } vector<int> inR(inorder.begin()+i+1, inorder.end()); inorder.erase(inorder.begin()+i, inorder.end()); preorder.erase(preorder.begin()); vector<int> preR(preorder.begin()+i, preorder.end()); preorder.erase(preorder.begin()+i, preorder.end()); TreeNode* root = new TreeNode(curVal); root->left = buildTree(preorder, inorder); root->right = buildTree(preR, inR); return root; } };
No comments:
Post a Comment