105. 从前序与中序遍历序列构造二叉树

一旦将递归难度升个级，我就真不会了，呜呜呜呜呜。好难过，这个题目我代码都看了好久。

题解：

1、就是先用一个map映射，映射的是中序遍历中每个值所对应的下标，注意这里不是下标对应节点值。然后我们再进行递归操作。

2、结束条件是：此时前序遍历的根节点的左边界大于右边界，也就是说，此时结点为空，没有左右子树，结束递归。因为题目给出的是数组，所以我们需要将数组和二叉树对应起来。

3、然后呢，根据前序遍历，那我们可以得到根节点，然后再根据中序遍历可以计算出当前节点的左子树的数量，通过递归构造左右子树即可。

4、我是被困在递归的边界条件了。preorder_left表示的是以前序遍历为基础的他的一个边界，同理，inorder_left表示的是以中序遍历为基础的，两者分开看，不要因为它看起来复杂就不看了，没关系，努力够够还是可以的。

代码：·

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> index;
public:
    TreeNode* myBuildTree(const vector<int>& preorder,const vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
        if(preorder_left>preorder_right) return nullptr;

        //根据前序遍历得到根节点
        int preorder_root=preorder_left; //下标
        //得到根节点在中序遍历的位置，也就是下标
        int inorder_root=index[preorder[preorder_root]];
        TreeNode *root=new TreeNode(preorder[preorder_root]);//建立新节点
        //算出当前的左子树的数量
        int size_left_subtree=inorder_root-inorder_left;
        //遍历左子树
        root->left=myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);
        //遍历右子树
        root->right=myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);
        return  root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=preorder.size();
        for(int i=0;i<n;i++){
            index[inorder[i]]=i;
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1); 
    }
};

人类的悲喜并不相通，好好努力，给自己赚底气，加油！！！