Given preorder and inorder traversal of a tree, construct the binary 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 *build(vector<int>&pre,int prestart,int preend,vector<int>&in,int instart,int inend) { if(preend<prestart||inend<instart||(preend-prestart)!=(inend-instart)) return NULL; TreeNode *head = new TreeNode(pre[prestart]); int rootpos; for(int i=0;i<=inend-instart;i++) if(in[i+instart]==pre[prestart]) { rootpos = i; break; } head->left = build(pre,prestart+1,prestart+rootpos,in,instart,instart+rootpos-1); head->right = build(pre,prestart+rootpos+1,preend,in,instart+rootpos+1,inend); return head; } TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { int presize = preorder.size(); int insize = inorder.size(); TreeNode *head = build(preorder,0,presize-1,inorder,0,insize-1); return head; } };