[LeetCode]Construct Binary Tree from Preorder and Inorder Tr

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

这道题要求根据二叉树的前序遍历序列和中序遍历序列构建二叉树。 举个例子： 前序序列：A B D E F C H I 中序序列：D B E F A C I H A是树的根节点，在中序序列中找到A 的位置，，则中序序列中A左边的序列构成结点A的左子树，A右边的序列构成结点A的右子树。对左右子树分别重复上述方式。 下面贴上代码：

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {return build(preorder,0,preorder.size(), inorder,0,inorder.size());}TreeNode* build(vector<int>& preorder,int pleft,int pright, vector<int>& inorder,int ileft,int iright){if (ileft==iright)return NULL;int i = ileft;while (preorder[pleft] != inorder[i]){i++;}TreeNode* tn = new TreeNode(inorder[i]);tn->left =build(preorder, pleft + 1, pleft + i – ileft, inorder, ileft, i);tn->right = build(preorder, pleft + i – ileft + 1, pright, inorder, i + 1, iright);return tn;}

一开始没注意两个vector 之前&，于是写出了Merry Limit Exceeded的代码QAQ，也贴上来吧：

class Solution {public:vector<int> getPart(vector<int>& v, int begin, int len){vector<int> ans;if (begin < v.size()){for (int i = 0; i < len; i++){ans.push_back(v[i + begin]);}}return ans;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){return build(preorder, inorder);}TreeNode* build(vector<int> preorder, vector<int> inorder){if (preorder.empty())return NULL;TreeNode* tn = new TreeNode(preorder[0]);vector<int>::iterator it = find(inorder.begin(), inorder.end(), preorder[0]);int mid = it – inorder.begin();int left = it – inorder.begin();int right = inorder.end() – 1 – it;tn->left = buildTree(getPart(preorder, 1, left), getPart(inorder, 0, left));tn->right = buildTree(getPart(preorder, left + 1, right), getPart(inorder, mid + 1, right));return tn;}};

如果有可能，我带你去远行。