题目描述

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

样例

前序遍历是：[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 index = 0;                       //前序遍历节点的下标
    unordered_map<int,int> position;       //快速在中序遍历中找到某值的下标
    TreeNode* build(vector<int>& pre, vector<int>& in, int inL, int inR)
    {                                 //[inL , inR] 是中序遍历的下标范围
        if(inL > inR) return NULL;  
        TreeNode* root = new TreeNode(pre[index]);   //根节点在前序遍历的前面
        int mid = position[ pre[index++] ];          //找到 根节点在中序遍历的下标  
        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) {
        for(int i = 0; i < inorder.size(); i++)
            position[inorder[i]] = i;  //离线 中序遍历值与下标的关系，
        return build(preorder, inorder, 0, inorder.size() - 1); 
    }  
};

Java代码

class Solution {

    int index = 0;
    Map<Integer,Integer> position = new HashMap<Integer,Integer>();

    public TreeNode dfs(int[] pre, int[] in, int inL, int inR){
        if(inL > right){
            return null;
        }
        int mid = position.get( pre[index] );
        TreeNode node = new TreeNode( pre[index++] );
        node.inL = dfs(pre, in, inL, mid - 1);
        node.inR = dfs(pre, in, mid + 1, inR);
        return node;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++){
            position.put(inorder[i],i);
        }
        return dfs(preorder, inorder, 0, inorder.length - 1);
    }
}