Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
» Solve this problemYou may assume that duplicates do not exist in the tree.
[Thoughts]
There is an example.
_______7______ / \ __10__ ___2 / \ / 4 3 _8 \ / 1 11
The preorder and inorder traversals for the binary tree above is:
preorder = {7,10,4,3,1,2,8,11} inorder = {4,10,3,1,7,11,8,2}
The first node in preorder alwasy the root of the tree. We can break the tree like:
1st round:
preorder: {7}, {10,4,3,1}, {2,8,11}
inorder: {4,10,3,1}, {7}, {11, 8,2}
_______7______
/ \
{4,10,3,1} {11,8,2}
Since we alreay find that {7} will be the root, and in "inorder" sert, all the data in the left of {7} will construct the left sub-tree. And the right part will construct a right sub-tree. We can the left and right part agin based on the preorder.
2nd roundleft part right part
preorder: {10}, {4}, {3,1} {2}, {8,11}
inorder: {4}, {10}, {3,1} {11,8}, {2}
_______7______ / \ __10__ ___2 / \ / 4 {3,1} {11,8}
see that, {10} will be the root of left-sub-tree and {2} will be the root of right-sub-tree.
Same way to split {3,1} and {11,8}, yo will get the complete tree now.
_______7______ / \ __10__ ___2 / \ / 4 3 _8 \ / 1 11
So, simulate this process from bottom to top with recursion as following code.
[Code]
1: TreeNode *buildTree(
2: vector<int> &preorder,
3: vector<int> &inorder) {
4: // Start typing your C/C++ solution below
5: // DO NOT write int main() function
6: return BuildTreePI(
7: preorder, inorder, 0, preorder.size()-1, 0, preorder.size());
8: }
9: TreeNode* BuildTreePI(
10: vector<int> &preorder,
11: vector<int> &inorder,
12: int p_s, int p_e,
13: int i_s, int i_e)
14: {
15: if(p_s > p_e)
16: return NULL;
17: int pivot = preorder[i_s];
18: int i =p_s;
19: for(;i< p_e; i++)
20: {
21: if(inorder[i] == pivot)
22: break;
23: }
24: TreeNode* node = new TreeNode(pivot);
25: node->left = BuildTreePI(preorder, inorder, p_s, i-1, i_s+1, i-p_s+i_s);
26: node->right = BuildTreePI(preorder, inorder, i+1, p_e, i-p_s+i_s+1, i_e);
27: return node;
28: }
No comments:
Post a Comment