代码如下：
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
限制：
0 <= 节点个数 <= 5000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题也是受启发较大的一道题，倒不是说具体的算法，而是一些指针的问题。没错，又是指针。。。。。
思路并不难，前序遍历序列preorder中第一个元素，必为根节点，记为root，然后去中序遍历序列inorder中寻找root，找到root之后，inorder左边为左子树，长度记为l，右边为右子树，长度记为r。然后分割preorder和inorder，preorder中取出长度为l和r的序列，代表新的子序列，inorder 中取出长度为l和r的序列，代表新的子序列，来确定新的根节点和子树。如下图所示：
代码如下（有错误，要看无错误的直接拉到最后）：
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
TreeNode* p;
// TreeNode n(0);
// p=&n;
p=div(preorder,inorder);
return p;
}
TreeNode* div(vector& preorder, vector& inorder)
{
if(preorder.size()==0)
return NULL;
TreeNode* p;
TreeNode n(preorder[0]);
p=&n;
//p=new TreeNode(preorder[0]);
int i,temp;
for(i=0;i in1;
vector pre1;
vector in2;
vector pre2;
for(int k=0;kleft=div(pre1,in1);
p->right=div(pre2,in2);
return p;
}
bool ifin1(int target,vector& in)
{
for(int i=0;i
提交会发现错误，错误如下：
=================================================================
==42==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x7ffe26d9ae48 at pc 0x00000037d668 bp 0x7ffe26d9ac30 sp 0x7ffe26d9ac28
READ of size 8 at 0x7ffe26d9ae48 thread T0
#4 0x7f98ae7660b2 (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Address 0x7ffe26d9ae48 is located in stack of thread T0 at offset 8 in frame
..........
查询资料，这个错误的出现是因为访问了边界外的内容，谁能访问边界外的内容，大概率是指针了，但我感觉我写的没问题，没有空指针和野指针的出现，怎么会访问边界外内容呢？
带着疑惑，我把代码复制到CLion中，设置测试用例，preorder={3,9,20,15,7}; inorder={9,3,15,20,7};会发现一个奇怪的现象:根节点3的左子树和右子树指向的是同一个地址，代码如下：
#include
#include "vector"
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector& preorder, vector& inorder);
bool ifin1(int target,vector& in);
TreeNode* div(vector& preorder, vector& inorder);
int main() {
vector preorder={3,9,20,15,7};
vector inorder={9,3,15,20,7};
buildTree(preorder,inorder);
return 0;
}
TreeNode* buildTree(vector& preorder, vector& inorder)
{
TreeNode* p;
// TreeNode n(0);
// p=&n;
p=div(preorder,inorder);
// p->left=NULL;
// p->right=NULL;
cout<val<left->val<right->val<& in)
{
for(int i=0;i& preorder, vector& inorder)
{
if(preorder.size()==0)
return NULL;
TreeNode* p;
// p=new TreeNode(preorder[0]);
TreeNode n(preorder[0]);
p=&n;
// p->val=preorder[0];
// cout<<"p->val is "<val<<" &p is "<<&p<<" n is "<<&n<<" n1 is "<<&n1<<" &a is "<<&a<val is "<val<<" &p is "<<&p< in1;
vector pre1;
vector in2;
vector pre2;
for(int k=0;kleft=div(pre1,in1);
p->right=div(pre2,in2);
cout<<"val is "<val<<" left is "<left<<" right is "<right<right "<right<
部分输出：
p->val is 9 &p is 0x16f7c3410
p->val is 20 &p is 0x16f7c3410
很显然，根节点3的左右节点，居然指向了同一个地址！我无法理解，查阅了诸多资料，终于找到了问题所在：
指针只是一个指针，它的诞生是为了指向一个地址，因此，只声明指针而不给出他的指向，是有问题的：
TreeNode* p;
p应该指向一个 TreeNode，无论这个TreeNode是malloc出来的，还是new出来的，还是TreeNode n声明出来的，这三种方式都可以在内存中开辟出一块地方，从而让p指向它。
但是三者是有区别的
1.malloc是在堆上动态分配内存，需要使用free进行释放
2.new是在自由存储区（free store）上为对象动态分配内存空间，自由存储区可以视为堆的一部分
3.声明则是在栈中分配内存
来看一看内存中
1、栈区（stack）
由编译器自动分配释放 ，存放函数的参数值，局部变量的值等，内存的分配是连续的，类似于平时我们所说的栈，如果还不清楚，那么就把它想成数组，它的内存分配是连续分配的，即，所分配的内存是在一块连续的内存区域内．当我们声明变量时，那么编译器会自动接着当前栈区的结尾来分配内存．
2、堆区（heap）
一般由程序员分配释放， 若程序员不释放，程序结束时可能由操作系统回收．类似于链表，在内存中的分布不是连续的，它们是不同区域的内存块通过指针链接起来的．一旦某一节点从链中断开，我们要人为的把所断开的节点从内存中释放．
3、全局区（静态区）（static）
全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 程序结束后由系统释放
4、文字常量区
常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区
存放函数体的二进制代码。
原文链接：https://blog.csdn.net/ll148305879/article/details/94391118
因此，变量声明的一个巨大问题就是：栈中的元素会随着函数结束而消失。因此，这也解释了为什了根节点3的左右子树指向了同一个地址。
div函数中，有这样一句：
TreeNode* p;
TreeNode n(preorder[0]);
p=&n;
直观上看没有错误，申请了 TreeNode指针，并指向了一个 TreeNode地址，但是，函数结束之后呢？该地址保存在栈中，函数结束会把栈中的一切给清空，那么请问指针p在函数结束后指向哪里？没人能知道，p实际上已经成为了一个野指针。
因此，应该改用这种方式：
TreeNode* p;
p=new TreeNode(preorder[0]);
new生成的 TreeNode，保存在堆中，因此，即使函数结束了，该地址仍不会消失，可以通过指针访问该地址。
因此，修改之后，可以顺利通过了：
class Solution {
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
TreeNode* p;
// 这里不用为p申请内存，因为p在之后会有指向，不会成为野指针。
// TreeNode n(0);
// p=&n;
p=div(preorder,inorder);
return p;
}
TreeNode* div(vector& preorder, vector& inorder)
{
if(preorder.size()==0)
return NULL;
TreeNode* p;
// TreeNode n(preorder[0]);
// p=&n;
p=new TreeNode(preorder[0]);
int i,temp;
for(i=0;i in1;
vector pre1;
vector in2;
vector pre2;
for(int k=0;kleft=div(pre1,in1);
p->right=div(pre2,in2);
return p;
}
bool ifin1(int target,vector& in)
{
for(int i=0;i
顺利通过，但是消耗时间太多了，只超过5%的人
之后看了看题解，题解里面提到可以把根节点用hashmap存储，来提升一下速度，稍后试一试这种方法
