第二天的leetcode刷题

今天上海热的要死，写题之前先发发牢骚，不然实在是没有办法静下心来好好写题，当时租房子的时候也没看好选的这个破地方，顶楼一扇无遮阳的小天窗，早上六点钟就能给你照醒，然后最主要也是最难搞的一点就是我爷爷没办法吹空调……外面多少度室内就多少度，只能开个风扇，然后一度电要你一块二。

讲真旅游就安安稳稳住宾馆，麻了兄弟们。

今天听啥？
听 breakfast

开始做题开始做题！！！

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

题目描述： 题目

所以题目是要求我们根据前序遍历和中序遍历的结果还原一个二叉树。

截图1
老规矩还是先看上面他给到的东西：
前面的跟之前一道题没有区别，都是构造一个二叉树，public里面的东西跟之前不同，这次改变了其中的参变量。

• Vector是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的数据的动态数组。
• int & preorder的意思就是一个整型变量的引用。
• vector<int> preorder的意思就是preorder是一个容器变量，这个容器叫vector，容器内存的数据是int型
• vector<int>& preorder的意思现在就很清楚了，preorder首先是个引用，引用的东西就是vector这个容器的变量，容器内部存着整型数据。

然后开始分析，首先前序遍历的第一个值就是根节点，然后根据中序遍历而分开左子树和右子树。这时候看到题解有个图非常nice我直接贴过来，题解的原本链接我放在后面了。

前序遍历
中序遍历
形象的二叉树前中遍历还原二叉树

所以通过前序和中序可以找到这棵二叉树的根节点、左子树以及右子树。
但是我卡住了，写了三遍都是编译不通过，整个代码流程应该是没问题的，麻烦是因为数组指针多了一点因为要一个一个排出来。

if (preorder.size() == 0)   return nullptr;//就是因为少加了一句判断，当前序遍历为0的时候直接输出空。

通过代码如下：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        if (preorder.size() == 0)   return nullptr;//判断
        TreeNode* root = new TreeNode(preorder[0]);
        int nums = 0;
        while (inorder[nums] != root->val)
            nums++;

        vector<int> preLeft(preorder.begin() + 1, preorder.begin() + nums + 1);
        vector<int> inLeft(inorder.begin(), inorder.begin() + nums);
        root->left = buildTree(preLeft, inLeft);

        vector<int> preRight(preorder.begin() + nums+ 1, preorder.end());
        vector<int> inRight(inorder.begin() + nums+ 1, inorder.end());
        root->right = buildTree(preRight, inRight);

        return root;

    }
};

> [引用题解图片链接](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/leetcode-105-cong-qian-xu-yu-zhong-xu-bi-3r09/)
P.S. 切片永远滴神，用指针真的烦到死，而且int* p;野良针！