105. Construct Binary Tree from Preorder and Inorder Traversal

已知前序序列和中序序列，构建二叉树。

解法：递归

TreeNode *build(vector<int>& preorder, int preStart, int preEnd, vector<int> &inorder, int inStart, int inEnd) { if(preStart > preEnd || inStart > inEnd) return NULL; int i = inStart; for(; i <= inEnd; ++i) { if(preorder[preStart] == inorder[i]) break; } TreeNode *p = new TreeNode(preorder[preStart]); int leftLen = i - inStart; p->left = build(preorder, preStart + 1, preStart + leftLen, inorder, inStart, i-1); p->right = build(preorder, preStart + 1 + leftLen, preEnd, inorder, i+1, inEnd); return p; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1); }