问题抽象

给定前序遍历和中序遍历，重建二叉树

算法：DFS

这道题的粗略思路很容易想到：先在前序遍历里找根节点，再在中序遍历定位到根节点，创建根节点，并确定左右子树的范围，再递归创建左右子树。

难点在于如何将粗略思路转化为精细的递归算法，转换的难点在于如何定义递归的参数？

关键点在于想到，构建每棵树都需要前序的一段数和中序的一段数，而且这两段数的个数相同！因此我们可以用pl, pr来代表前序遍历这段数的左右边界，il, ir来代表中序遍历这段数的左右边界。

还有一个关键点，就是我们如何在递归中缩减规模？即如何找当前树的左、右子树在前、中序遍历的左右边界？只需要找到左、右子树的个数！如何找到左、右子树的个数？在中序遍历中定位根节点，根节点左边的数的个数（只包含当前中序遍历这段数）就是左子树的个数，剩下的数就是右子树的个数（实际上只需要左子树的个数，除去左子树和根节点，剩下的数必定为右子树）！

时间复杂度

用一个哈希表存储中序遍历每个数的位置，时间复杂度$O(N)$

代码

/**
 * 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> pos;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size();i ++){
            pos[inorder[i]] = i;
        }
        int n = inorder.size();
        return dfs(preorder, inorder, 0, n-1, 0, n-1);
    }

    TreeNode* dfs(vector<int> &preorder, vector<int> &inorder, int pl, int pr, int il, int ir){
        if(pl > pr) return NULL;
        int k = pos[preorder[pl]] - il; // 左子树的长度
        TreeNode *root = new TreeNode(preorder[pl]);
        root->left = dfs(preorder, inorder, pl+1, pl+k, il, il+k-1);
        root->right = dfs(preorder, inorder, pl+k+1, pr, il+k+1,ir);
        return root;
    }
};