题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

大致思路

pre = {根节点，左子树，右子树}

vin = {左子树，根节点，右子数}

前序列表中第一个是二叉树的根节点，由于题目中数据都不重复，那么我们找到中序列表中的根节点的位置，那么左边部分就是左子树的全部，右边就是右子树的全部元素。然后利用递归就可以得到最终的二叉树了。

代码

TreeNode* reConstructBinaryTree(vector
    
      pre, vector
     
       vin) {	size_t pre_len = pre.size(), vin_len = vin.size();	if ( vin_len == 0 ||  pre_len == 0){		return NULL;	}	TreeNode *temp_ptr = new TreeNode(pre[0]);	vector
      
        l_pre, l_vin, r_pre, r_vin;	int mid = -1;	for (size_t i = 0; i < vin_len; ++i){		if (vin[i] == pre[0]){			mid = i;			continue;		}		if (mid < 0){			l_vin.push_back(vin[i]);		}		else{			r_vin.push_back(vin[i]);		}				}	for (size_t i = 1; i < pre_len; ++i){		if (i <= mid){			l_pre.push_back(pre[i]);		}		else{			r_pre.push_back(pre[i]);		}	}	temp_ptr->left = reConstructBinaryTree(l_pre, l_vin);	temp_ptr->right = reConstructBinaryTree(r_pre, r_vin);	return temp_ptr;}复制代码
      
     
    

总结

这道题整体思路熟悉二叉树的前中后遍历方法的话，还是比较简单的，但是如果只是大概了解的话，可能写代码的过程中还是会被卡两下的，特别是个别的地方，找根节点的位置的时候，之前把 mid 声明称 size_t 因为编译器警告下面的判断类型不匹配。结果就踩到坑中还半天不自知，最后想了想，算了还是声明成负数，简单而且正常也不会出现啥问题啊 手动滑稽。