/**Passed both small and large judge. Not so many surprise here, just pay extra attention to the boundary indices. * 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* build(vector<int> const& preorder, int const pre_first, int const pre_last, vector<int> const& inorder, int const in_first, int const in_last){ if (in_first > in_last) return NULL; TreeNode* root = new TreeNode(preorder[pre_first]); if (in_first == in_last) return root; size_t const r_in = distance(inorder.begin(), find(inorder.begin()+in_first, inorder.begin()+in_last, root->val)); size_t const sizeLeft = r_in - in_first;//size of left subtree root->left = build(preorder, pre_first+1, pre_first+sizeLeft-1, inorder, in_first, r_in-1); root->right = build(preorder, pre_first+sizeLeft+1, pre_last, inorder, r_in+1, in_last); return root; } TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { // Start typing your C/C++ solution below // DO NOT write int main() function return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1); } };
Solving problems is fun. But solving the same problem over and over is pain. Once solved, forever solved.
sourcecode
Saturday, November 24, 2012
Construct Binary Tree from Preorder and Inorder Traversal
http://www.leetcode.com/onlinejudge
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment