Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]Return the following binary tree:
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() == 0 || inorder.size() == 0) return NULL; int value = preorder[0]; TreeNode* root = new TreeNode(value); vector<int> inorderL; vector<int> inorderR; bool flag = true; int index = 0; for(int i = 0; i < inorder.size(); i++) { if(inorder[i] == value) { flag = false; index = i; } if(flag) inorderL.push_back(inorder[i]); else if(i>index) inorderR.push_back(inorder[i]); } vector<int> preorderL; vector<int> preorderR; for(int j = 1; j < preorder.size(); j++) { if(j<index+1) preorderL.push_back(preorder[j]); else preorderR.push_back(preorder[j]); } root->left = buildTree(preorderL,inorderL); root->right = buildTree(preorderR,inorderR); return root; } };
