给定一个二叉树前序遍历数组A 124367，中序遍历得到数组B, 421637。我们的任务是从这两个结果中构造出原来二叉树。 根据前序遍历的顺序，可以知道数组是先存放根，然后是左子树，最后是右子树。 根据中序遍历的顺序，可以知道数组是先放左子树，然后是根，最后是右子树。 根据定义，前序遍历数组第一个位置是根节点，但左子树和右子树大小未知。而中序遍历一旦确定根的位置，就可以确定左右子树的大小。这两者刚好是互补关系。 因此具体过程是 - 用前序数组的第一个位置确定中序数组的根位置 - 将中序数组分成两个部分，得到左右子树的大小。 - 用左右子树的大小确定前序数组的左右子树位置 - 对于新生成的左右子树，用上面方法确定新的根位置和左右子树大小。 对于本问题，就是1将421637分成42和637,这意味着左子数大小为2，右子数大小为3.于是124367被分成1，24，367. 24和42是新的左子树问题，367和637是新的右子树问题。 理清思路之后，我们可以按照递归模版四步走起来 第零步：思考函数名和传递的参数和全局变量。根据我们的分析，我们最重要的就是子问题对应数组的区间，也就是我们需要记录前序数组的左右子树开始和结束(pb, pe), 中序数组的开始和结束(ib, ie), 函数名的话，就写dc吧 第一步：终止条件。这里终止条件是前序数组用完了（当然中序数组肯定也用完了） ```c if (pb > pe) return NULL; ``` 第二步: 处理逻辑。每次用前序节点的第一个位置构建根节点，然后拆分中序节点，获取左右子树的大小， ```c TreeNode *root = new TreeNode(preorder[pb]); int rootIndex = mp[root->val]; //获取中序的位置 int leftSize = rootIndex - ib; //左子树大小 int rightSize = ie - rootIndex; //右 ``` 第三步，下潜一层, 新的一层要带新的参数过去。 ```c root->left = dc(preorder,pb+1,pb+leftSize, inorder,ib, rootIndex-1); root->right = dc(preorder,pb+leftSize+1, pe, inorder, rootIndex+1, ie); ``` 第四步：状态重置。此处不需要 最终返回root即可。 对应的完成代码见 <https://github.com/xuzhougeng/algorithm006-class01/blob/master/Week_02/G20200343030533/LeetCode_105_533.cpp>