剑指offer题目训练5：重建二叉树

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

• 二叉树中每个节点的值都互不相同；

• 输入的前序遍历和中序遍历一定合法；

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：    3
   / \  9  20
    /  \   15   7

/**
 * 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) {
        //记录下根节点在中序的位置
        int n=preorder.size();
        for(int i=0;i<n;i++){
            pos[inorder[i]]=i; //inorder[i]表示inorder[i]前序根节点的位置
        }
        return buildChild(preorder,inorder,0,n-1,0,n-1);
    }
    TreeNode* buildChild(vector<int>&  preorder, vector<int>& inorder,int preStart,int preEnd,int inStart,int inEnd){ 
        if(preStart>preEnd) return NULL;
        TreeNode* root=new TreeNode(preorder[preStart]);
        int k=pos[preorder[preStart]]-inStart;//中序起点到根节点个数
        //左孩子前序范围prestart+1~prestart+k  中序范围:inStart~k-1    
        root->left=buildChild(preorder,inorder,preStart+1,preStart+k,inStart,inStart+k-1);
        //右孩子前序范围prestart+k+1~preend,中序范围 k+1,inEnd
        root->right=buildChild(preorder,inorder,preStart+k+1,preEnd,inStart+k+1,inEnd);
        
        return root;
    }
};

1. 思路，二叉树建树要想到的思路就是要自底向上建树，自然需要用到递归思想，即先建左右子树，再连上根节点。

2. 首先利用前序遍历找到根节点，前序的第一个数就是根节点

3. 在中序中找到根节点位置k，k左边就是左子树的中序遍历，右边就是右子树的中序遍历

4. 计算下左子树中序遍历长度L,在前序中根节点后面的L个数就是左子树的前序遍历，剩下的就是右子树的前序

5. 根据左右子树的前序和中序，递归创建左右子树

6. 创建根节点，完成