题目描述

给定一棵二叉树的前序遍历和中序遍历，请复原出整棵二叉树。
注意：二叉树中没有值相同的节点。

样例

前序遍历是：[3,9,20,15,7]
中序遍历是：[9,3,15,20,7]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

算法

(递归) $O(n)$

(搬来了yxc大佬的题解和代码，删改了一下)

中序遍历的特点： 左根右，既根节点的左右两侧分别是其左子树，右子树
前序遍历的特点： 根左右，既根节点在前面

具体步骤如下：

1. 先利用前序遍历找根节点 ( 根节点在前序遍历的前面 );
2. 在中序遍历中找到根节点的位置mid ( 则mid左边是左子树，右边是右子树 )；
3. 得到左右子树的范围后，我们先递归创建出左右子树，然后再创建根节点；

C++ 代码

class Solution {
public:
    int pr = 0;                       //前序遍历节点的下标
    unordered_map<int,int> idx;       //快速在中序遍历中找到某值的下标
    TreeNode* build(vector<int>& pre, vector<int>& in, int inL, int inR)
    {                                 //[inL , inR] 是中序遍历的下标范围
        if(inL > inR) return NULL;  
        TreeNode* root = new TreeNode(pre[pr]);      //根节点在前序遍历的前面
        int mid = idx[ pre[pr++] ];                  //找到 根节点在中序遍历的下标  
        root->left  = build(pre, in, inL, mid - 1);  //创建左子树 [inL , mid -1]
        root->right = build(pre, in, mid + 1, inR);  //创建右子树 [mid + 1, inR]     
        return root;  
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i++)
            idx[inorder[i]] = i;  //离线 中序遍历值与下标的关系，
        return build(preorder, inorder, 0, n - 1); 
    }  
};