本文共 1126 字，大约阅读时间需要 3 分钟。

从遍历结果来反推二叉树 ，关键是从遍历数组中找到规律。我们可以把二叉树看做很多个树枝（即三个节点构成）构成的结构，所以我们每次只要找到每个树枝怎样构成，然后递归就可以了。

1.首先要找到根节点。前序遍历的第一个元素即为根节点，记为s1。 2.找到左子节点。在前序遍历中，根节点的后一个元素即为左子节点，记为s1+1; 3.找到右子节点。在前序遍历中，顺序是：根节点——左子节点——左子节点全部子节点——右子节点-—右子节点的全部子节点。将左子节点的全部子节点的长度设为leftlen，所以右子节点在前序遍历中的位置即为s1+leftlen+1；那么左边二叉树总共有多少个节点呢？这需要从中序遍历中得到。在中序遍历中根节点将左右子树分开，设中序遍历起始元素位置s0，根节点位置mid，所以leftlen的长度即为mid-s0； 4,在完成一个树杈的重建后，我们需要进行下一个树杈的重建。对于左子树来讲：根节点位于前序遍历中的s1+1，元素位置放于中序遍历s0到mid-1。对于右子树来说，根节点位于前序遍历中的s1+leftlen+1，元素位置存放于中序数组的mid+1至e0。 5.从上面可以看到，求得一个树杈需要的信息有：两个遍历数组pre和in，前序遍历数组中根节点的位置s1，中序遍历起始终止节点位置s0,e0。所以我们可以通过输入这五个信息，将这个过程不断递归。结束条件为s0>e0，这意味着子树中没有元素，返回nullptr。

TreeNode* reConstructBinaryTree(vector
   
     pre,vector
    
      vin) {
   	unordered_map
     
       in;	if(pre.empty ())		return nullptr;	for(int i=0;i
      
        &m,vector
       
         &pre,int s0,int e0,int s1){
      if(s0>e0)   {
   	   return nullptr ;   }   int mid=pre[s1];   int index=m[mid];   int leftlen=index-s0-1;   TreeNode *node=new TreeNode (mid);   node->left=buildtreehelper (m,pre,s0,index-1,s1+1);   node->right =buildtreehelper(m,pre,index+1,e0,s1+leftlen+2);   return node;}
       
      
     
    
   

转载地址：http://widmi.baihongyu.com/