105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3 / \ 9 20 / \ 15 7 /** * Definition for a binary tree node. * 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) { int n = preorder.size(); return buildTree(preorder, 0, n-1, inorder, 0, n-1); } TreeNode* buildTree(vector<int> &preorder, int pleft, int pright, vector<int> &inorder, int ileft, int iright) { if(pleft > pright || ileft > iright) return NULL; TreeNode *curr = new TreeNode(preorder[pleft]); int i; for(i = ileft; i <= iright; ++i) { if(inorder[i] == curr->val) break; } curr->left = buildTree(preorder, pleft + 1, pleft + i -ileft, inorder, ileft, i -1); curr->right = buildTree(preorder, pleft + i - ileft + 1, pright, inorder, i + 1, iright); return curr; } };