解题思路
对于二叉树的重建问题,我们首先需要明确的是给定的两个遍历数组的每个数字代表了什么;
对于前序遍历是【根,左,右】
对中序遍历是【左,根,右】
下面的思路就是一个分治的思想了,我们可以根据中序遍历分治出左右两边一个更小的树,这个子树根分治前的树
性质是完全一样的,有了这个思路的就可以进行,代码的编写了
对于dfs的每次递归,其中的参数都会逐渐的缩小范围,直到最终没有了子节点返回空节点
对于逐渐缩小的范围,应用左右两个下标指针就可以表示了;
具体代码如下:
代码
class Solution {
public:
map<int,int> mymap;
TreeNode* dfs(vector<int>& pre, vector<int>& in,int pl,int pr,int il,int ir){
if(pl > pr) return nullptr;
TreeNode* root = new TreeNode(pre[pl]);//将序遍历的对应根节点new出来
int mid_index = mymap[pre[pl]]; //在中序遍历序列中寻找根节点的位置,从而确定其左右子树的划分
int lef_len = mid_index - il; //求出其左子树的长度,方便下面进行递归
root->left = dfs(pre,in,pl+1,pl + lef_len,il,mid_index - 1); //根据递归求出其子序列中的子树
root->right = dfs(pre,in,pl + lef_len + 1,pr,mid_index + 1,ir);
return root;
}
TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
int pl = 0,il = 0;
int pr = pre.size() - 1 , ir = in.size() - 1;
for(int i = 0 ;i<ir+1;i++) mymap[in[i]] = i; //构建一个由值指向下标的哈希表
return dfs(pre,in,pl,pr,il,ir);
}
};