【牛客网】剑指offer编程题：重建二叉树（C++）

 前序遍历：先访问根节点，在访问左节点，最后访问右节点。、

 遍历结果：ABDFECGHI

中序遍历：先访问左节点，再访问根节点，最后访问右节点。

遍历结果：DBEFAGHCI

      在这个题目中要充分利用先序遍历和中序遍历的特点，先序遍历（根左右）找到根节点的位置，中序遍历（左根右）找到左子树的长度。利用递归重建二叉树。

代码：
class Solution {
public:
    unordered_map<int, int> pos;   //Map记录元素在中序遍历中的位置（便于计算左右子树的长度）
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();  //记录结点个数
        for (int i = 0; i < n; i++)
            pos[vin[i]] = i;
        return dfs(pre, vin, 0, n - 1, 0, n - 1);//递归函数，重建二叉树。
    }
    
    TreeNode* dfs(vector<int> pre, vector<int> vin, int pl, int pr, int vl, int vr)
    {   // pl,pr 前序遍历的左右边界，vl,vr 中序遍历的左右边界
        // pre先序遍历(根左右) vin中序遍历（左根右）
        if (pl > pr) return NULL;
        //找根节点
        TreeNode* root = new TreeNode(pre[pl]); //先序遍历找根节点
        //左子树长度k
        int k = pos[pre[pl]] - vl;
        root -> left = dfs(pre, vin, pl + 1, pl + k, vl, vl + k - 1);
        root -> right = dfs(pre, vin, pl + k + 1, pr, vl + k + 1, vr);
        return root;
    }
    
};