给定前序遍历和中序遍历，要求重建二叉树
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
算法思路是从前序遍历中找到树的根节点，然后在中序遍历中划分出左右子树，从前序遍历中再找到子树的根节点，然后从中序遍历中划分出子树的左右子树，循环往复。在递归回溯的时候将左右子树赋值给根节点的左右子树指针。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int nowPos = 0;
TreeNode *rebuildTree(vector<int> inOrder, vector<int>preOrder, int l, int r){
if(l > r){
return NULL;
}
TreeNode *tree = new TreeNode(preOrder[nowPos]);
int i = l;
//找子树根节点在中序遍历中的位置
for(; i<=r; i++){
if(inOrder[i] == preOrder[nowPos]){
break;
}
}
nowPos++;
//回溯赋值子树
tree->left = rebuildTree(inOrder, preOrder, l, i-1); //划分左右子树
tree->right = rebuildTree(inOrder, preOrder, i+1, r);
return tree;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
return rebuildTree(vin, pre, 0, pre.size()-1);
}
void postTraversal(TreeNode *nowPtr){
if(nowPtr == NULL){
return;
}
postTraversal(nowPtr->left);
postTraversal(nowPtr->right);
cout<<"node:"<<endl;
cout<<nowPtr->val<<endl;;
}
};
原文：https://www.cnblogs.com/chengsheng/p/10602063.html