根据一棵树的前序遍历与中序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。
例如,给出
前序遍历 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) { if(!preorder.size()) return NULL; int middle = preorder[0]; vector<int> preleft; vector<int> preright; vector<int> inleft; vector<int> inright; int i, j; i = 0; j = 1; for(;i < inorder.size();i++){ if(inorder[i] != middle) inleft.push_back(inorder[i]); else break; } i++; for(;i < inorder.size();i++){ inright.push_back(inorder[i]); } for(;j <= inleft.size();j++){ preleft.push_back(preorder[j]); } for(;j < preorder.size();j++){ preright.push_back(preorder[j]); } TreeNode* T = new TreeNode(middle); T->left = buildTree(preleft, inleft); T->right = buildTree(preright, inright); return T; } };