主题：
givenpreorderandinordertraversalofatree，construct the binary tree。
Note:
youmayassumethatduplicatesdonotexistinthetree。
根据前相遍历和中相遍历的结果构建二叉树。
思想分析：
通过分析二叉树的前相遍历和中相遍历结果，发现：
二叉树前遍历的第一个节点是根节点。
在中顺遍历中找到根节点，并在根节点上进行划分。 中顺序遍历左侧是左侧子树中顺序遍历的结果(有x个节点)，右侧是右侧子树遍历的结果(有y个节点)。
前向遍历除了第一根节点、x节点之外，这x个节点是左半部分树前向遍历的结果，其馀节点(必须是y个)是右半部分树前向遍历的结果。
这样就得到了pbdtn的前相横移和中相横移的结果，所以回到了原来的问题。 这样自然而然地想到了递归。
c代码：
/* * definitionforbinarytree * struct treenode { * intval； * TreeNode *left； * TreeNode *right； *treenode(intx ) : val(x ) left ) null )、right ) {} * }； */class solution { private : treenode * make node (vector int :3360 iteratorprebegin，vector int 33603360 iteratorpreeend vece vector int :3360身份验证(if (pre begin==preend ) return nullptr； //根据中序遍历结果查找根节点(根节点在前序遍历中是第一个节点)； treenode * root=new treenode (it root )； //要计算根的左子树节点个数的int leftSize=itRoot - inBegin； //中顺序遍历结果、根节点左侧为左部分树的中顺序遍历的结果、右侧为右部分树的中顺序遍历的结果//前顺序遍历的结果、除了根节点之外的前leftSize个节点为左部分树的前顺序遍历的结果， 如果后面节点是右部分树的前序遍历的结果root-left=makenode(prebegin1，prebeginlling root-right=make node (prebeginleftsize 1，preEnd，preEnd 返回根； } public : treenode * build tree (vectorintpreorder，vectorint inorder ) if ) preorder.empty ) ) return nullptr； treenode * root=make node (preorder.begin )、preorder.end (in order.begin )、inorder.end ) )； 返回根； }； 其中，find函数的签名如下：
template class InputIterator，classtinputiteratorfind (inputiteratorfirst，InputIterator last，const T val )； findvalueinrangereturnsaniteratortothefirstelementintherange [ first， last] thatcomparesequaltoval.ifnosuchelementisfound thefunctionreturnslast.thefunctionusesoperator==tocomparetheindividualelemem 0迭代器这样的写法很冗长，很长，而且也可以使用typedef进行写法的简化。
class solution { private : templatetypenamettreenode * make node (tprebegin，T preEnd，T inBegin，T inEnd ) if } pre begin=aame treenode * root=new treenode (it root )； int leftSize=itRoot - inBegin； 根节点(pre begin 1，preBegin leftSize 1，inBegin，itRoot )； root-right=make node (prebeginleftsize 1，preEnd，itRoot 1，inEnd )； 返回根； } public : treenode * build tree (vectorintpreorder，vectorint inorder ) if ) preorder.empty ) ) return nullptr； treenode * root=make node (preorder.begin )、preorder.end (in order.begin )、inorder.end ) )； 返回根； }； Java参考代码：
想法与上述相同，但要从数组中选择具有Java的元素，需要进行遍历。 (也可以转换为List或Set，但导线测量效率最高。 )上面的c代码使用了查找函数。
有时会觉得c代码还很简洁！
/* * definitionforbinarytree * public class treenode { * intval； * TreeNode left； * TreeNode right； *treenode(intx ) { val=x； } */public class solution { privatetreenodemakenode (int [ ] preorder，int preBegin，int preEnd，int[] inorder，intin int for(intI=inbegin； i inEnd； I ) if (in order [ I ]==preorder [ pre begin ] ) { index=i； } } int leftSize=index - inBegin； treenode root=new treenode (preorder [ pre begin ] )； root.left=makenode(preorder，preBegin 1，preBegin leftSize 1，inorder，inBegin，inBegin leftSize )； root.right=makenode(preorder，preBegin leftSize 1，preEnd，inorder，index 1，inEnd )； 返回根； } publictreenodebuildtree (int [ ] preorder，int[] inorder ) if ) preorder.length==0) return null； treenoderoot=makenode(preorder，0，preorder.length，inorder，0，inorder.length )； 返回根； }