二叉树前序序列中序序列后序序列,二叉树的先序序列和中序序列

1 基本思路：前序遍历的第一个节点为根节点，找到根节点在中序遍历中的位置i。然后分别找到前序遍历中左子树对应的部分，前序遍历中右子树对应的部分，中序遍历中左子树对应的部分，中序遍历中右子树对应的部分，分别用四个数组来存储。然后分别对左子树、右子树递归调用，传入的参数也对应发生改变。
2 代码实现：

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* reConstructBinaryTree(vector<int>pre,vector<int>in) { //考虑边界情况：由于pre和in的size总是相同 int inlen=in.size(); if(inlen==0) return NULL; //先序遍历序列的首元素是根节点 TreeNode * head=new TreeNode(pre[0]); //查找根节点在中序遍历序列中的位置，pos用来存储这个位置 int pos=find(in.begin(),in.end(),pre[0])-in.begin(); //用left_pre存储前序序列中的左子树，left_in存储中序序列中的左子树 //用right_pre存储前序序列中的右子树，right_in存储中序序列中的右子树 vector <int> left_pre,left_in,right_pre,right_in; for(int i=0;i<pos;i++) { left_in.push_back(in[i]); left_pre.push_back(pre[i+1]); } for(int i=pos+1;i<inlen;i++) { right_in.push_back(in[i]); right_pre.push_back(pre[i]); } //将左子树的前序中序序列传入，递归构建左子树 head->left=reConstructBinaryTree(left_pre,left_in); head->right=reConstructBinaryTree(right_pre,right_in); //每次递归调用返回根节点 return head; }};

3 注意事项：
①需要考虑边界情况，即当左子树序列或者右子树序列元素的个数为0的时候，返回值为空
②使用find()-in.begin()获取根元素在中序序列的位置，因为find()的返回值和begin()是同种类型，所以可以做运算。
③前序序列和中序序列分别对应的左子树和右子树的范围及更新是递归的前提
④每次递归调用都返回当前树的根节点。
4 语法收获：
①可以对vector的begin()和end()取内容(*)获得数组的首尾元素，注意end需要减1
②查找数组中是否有值为XX的元素并返回其下标
int i=find(a.begin(),a.end(),val)-a.begin()
使用find时添加头文件algorithm
find返回值是vector对应的迭代器类型,与begin()返回值类型相同，所以可以做运算
③ vector类型的好处是既可以通过指针访问，也可以通过下标访问
④不管是链表的节点还是树的节点，都可以在结构体内加一个构造函数，方便创建节点的时候直接初始化。
例如：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
构造函数中使用参数列表初始化成员，注意参数列表的基本格式。
5 报错记录
编译报错：too few arguments to function call,expected 6,have 2
报错原因：形参和实参个数不符 收获：牛客网剑指offer的题目要严格按照它的定义来，因为是按照它的定义来测试用例的，如果修改，用例会因为参数传递不通过。

TikTok半月报来了vscode配置远程开发环境并远程调试运行C++代码的教程