轉載自：http://blog.csdn.net/sbitswc/article/details/26433051

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

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

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 round
left 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. c++

[cpp] view plain copy

TreeNode?*BuildTreePI(??

????vector<int>?&preorder,??

????vector<int>?&inorder,??

????int?p_s,?int?p_e,??

????int?i_s,?int?i_e){??

????if(p_s?>?p_e)?return?NULL;??

????int?pivot?=?preorder[p_s];??

????int?i?=?i_s;??

????for(;i<i_e;i++){??

????????if(inorder[i]?==?pivot)??

????????????break;??

????}??

????int?length1?=?i-i_s-1;??

????int?length2?=?i_e-i-1;??

????TreeNode*?node?=?new?TreeNode(pivot);??

????node->left?=?BuildTreePI(preorder,inorder,p_s+1,length1+p_s+1,i_s,?i-1);??

????node->right?=?BuildTreePI(preorder,?inorder,?p_e-length2,?p_e,?i+1,?i_e);??

????return?node;??

}??

TreeNode?*buildTree(vector<int>?&preorder,?vector<int>?&inorder)?{??

????return?BuildTreePI(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);??

}??

java

[java] view plain copy

public?TreeNode?buildTree(int[]?preorder,?int[]?inorder)?{??

????????return?buildPI(preorder,?inorder,?0,?preorder.length-1,?0,?inorder.length-1);??

????}??

????public?TreeNode?buildPI(int[]?preorder,?int[]?inorder,?int?p_s,?int?p_e,?int?i_s,?int?i_e){??

????????if(p_s>p_e)??

????????????return?null;??

????????int?pivot?=?preorder[p_s];??

????????int?i?=?i_s;??

????????for(;i<i_e;i++){??

????????????if(inorder[i]==pivot)??

????????????????break;??

????????}??

????????TreeNode?node?=?new?TreeNode(pivot);??

????????int?lenLeft?=?i-i_s;??

????????node.left?=?buildPI(preorder,?inorder,?p_s+1,?p_s+lenLeft,?i_s,?i-1);??

????????node.right?=?buildPI(preorder,?inorder,?p_s+lenLeft+1,?p_e,?i+1,?i_e);??

????????return?node;??

????}?

總結

以上是生活随笔為你收集整理的按照前序遍历和中序遍历构建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。