《剑指Offer》 根据前序遍历和中序遍历确认二叉树

更好的题解

https://cloud.tencent.com/developer/article/1496104

思路是这样的：1：根据前序遍历来确定每次根节点的位置，因为前序遍历先访问的是根节点，所以前序遍历第一个位置就是根节点。 2：根据根节点和中序遍历将树划分为左右两棵树。3：根据第一步和第二步递归的处理左右两棵树。

第一步：根据前序遍历 A B D E G C F H 确定头结点是A，根据中序遍历 D B G E A C H F 将树划分为左子树 D B G E 和右子树 C H F。
第二步：划分为左右两棵子树：对于左子树，前序遍历是 B D E G，中序遍历是 D B G E。对于右子树，前序遍历是 C F H，中序遍历是 C H F。
第三步：对左子树和右子树分别运用第一步和第二步进行分析。
递归结束的条件：当中序遍历的节点只剩下一个节点的时候，那么这个节点就是叶子节点。

整体的操作流程如下：

/**

`* Definition for binary tree

`* struct TreeNode {

`*     int val;

`*     TreeNode *left;

`*     TreeNode *right;

`*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}`

`* };

*/

class Solution {

public:

struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {

int inlen = in.size();

if (inlen == 0)

return NULL;

vector<int> left_pre,right_pre,left_in,right_in;

//创建根节点，根节点肯定是前序遍历的第一个数`

TreeNode* head = new TreeNode(pre[0]);

//找到中序遍历根节点所在位置,存放于变量gen中

int gen=0;

for (int i = 0;i < inlen; i++) {
if (in[i] == pre[0]) {
gen=i;
break;
}
}

//对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边

//利用上述这点，对二叉树节点进行归并

for (int i = 0;i < gen; i++) {
left_in.push_back(in[i]);
left_pre.push_back(pre[i+1]);//前序第一个为根节
}

for (int i = gen+1; i < inlen; i++) {
right_in.push_back(in[i]);
right_pre.push_back(pre[i]);
}

//和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树`

//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点`

head->left = reConstructBinaryTree(left_pre,left_in);

head->right = reConstructBinaryTree(right_pre,right_in);

return head;

}

};