当前位置 博文首页 > 中流击水，浪遏飞舟：dfs&&剑指 Offer 07. 重建二叉树
目的：给出前序遍历和中序遍历的结果，且不包含重复数字，求出原始二叉树。
思路：二叉树前序遍历的第一个结点为根节点，依据中序遍历找到根节点，此时中序遍历根节点左边全部是左子树，右边全部是右子树。按照这么个递归分治，最终重建二叉树，不过二叉树的边界挺难看懂，想半天。。
dfs：（1）递归参数；（2）递归终止条件；（3）递推工作。
心得：太难了，看题解都得看半天，最后才差不多研究出那么一回事。
注意：按照前序遍历理解传递的参数：根结点root，左子树的左边界left，右子树的右边界right。每次在根结点处建立新节点值，当left>right时返回。
参考：
面试题07. 重建二叉树（递归法，清晰图解）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int,int> div; //哈希表记录中序遍历的索引值，每次找到对应索引值，很快划分左右子树
TreeNode* dfs(int root,int left,int right,vector<int>& preorder){ //参数：根，左子树的左边界，右子树的右边界,前序遍历数组
if(left>right){
return NULL; //递归终止条件
}
int i=div[preorder[root]]; //找到中序遍历的根节点
TreeNode*node=new TreeNode(preorder[root]); //建立新根节点
node->left=dfs(root+1,left,i-1,preorder); //按前序遍历看左子树的root
node->right=dfs((i-1-left)+root+1+1,i+1,right,preorder); //按前序遍历看右子树的root
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i=0;i<inorder.size();i++){
div[inorder[i]]=i;
}
return dfs(0,0,inorder.size()-1,preorder);
}
};
