1.*数据结构：字典树/前缀树/Trie树-immutable；红黑树/对称二叉B树；AVL/二叉平衡查找树；二叉查找/排序/搜索树；最大/小堆-优先队列；二叉树；树；
2.*基础算法：
https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-algorithm.md
3.*思路：
(1)没有排序则先排序！！！
(2)O(n) 时间复杂度& O(1) 空间复杂度||两数和:双指针（滑动窗口）
①while(l<r){operate(l,r);
if(左右移动判断)l++;else r--;}
(3)层序遍历+布满二叉树
(4)数组下标：map
(5)数组相同元素：异或为0，异或满足结合律交换律；异或非0则两个不同数必有一位bit不同，此bit位为分组条件
(6)不要求空间复杂度：map,hash,set
①map<共同特点，存放数组>：
1)比如排序后字符串一样（共同特点）
2)//map<string,vector<string>> m + vector<vector<string>> res
3)//改成map<string,int(表示res第一维下标)> m + vector<vector<string>> res
(7)二分法查找
(8)二叉搜索树:
①中序遍历->有序数组处理
②没有值相同的节点
(9)需要比较大小时,边界值最好设置long long型,即LLONG_MIN,ULLONG_MIN
①一般认为(unsigned)+(int=long int=long)=32bit;long long=long long int=64位
②INT_MIN,UINT_MIN,LONG_MIN,ULONG_MIN
③
4.主要思想对比
(1)总结（遇到二叉树问题）：
①考虑顺序(
1)考虑前中后序遍历
2)考虑前中后序遍历+pre前驱节点
3)考虑前中后 逆序遍历（+pre)，比如逆前序：根左右->右左根
4)考虑前中后 变序遍历（+pre)，比如变前序：根左右->根右左
②考虑递归<
③迭代（时间空间都O(n)）<
④morris（空间O(1),但不在遍历中途必须线索都解锁了才能返回，否则必须遍历到          结束才能返回）
(2)动态规划(最值+最优子结构+重叠子问题+状态转移方程+枚举+自下而上）：https://labuladong.github.io/ebook/动态规划系列/动态规划详解进阶.html
①状态转移方程
1)画表格推导：1+2+3+...+99,左到右，小到大
2)维度确定：一个变量加一维，变量枚举总数就1或2可以省略一维用两个少一维数组表示节省一个循环
3)1~2个如下转移方程
s[0...i...n-1][看情况][选择与不选择:2]=max(s[][][],operate(s[][][],nums[i]))）
可以是i和i-1项有关系，也可以是i和前面很多项有关系，未必差一项
4)最值+最优子结构+重叠子问题：
a.一个数组/字符串/子序列
a)dp[i]:以i为尾的...
b)dp[i][j]:SelArray[i,i+1,,,j-1,j]
i.一般与dp[i+1][j-1],dp[i][j-1],dp[i+1][j]有关
b.两个数组/字符串/子序列
a)dp[i][j]:SelArray1[0~i] SelArray2[0~j]
i.一般与dp[i-1][j-1],dp[i-1][j],dp[i][j-1]有关
c.博弈问题：dp[i][2]/dp[i][j][2] 0表示先手获得最高分，1表示后手获得最高分
②临界条件：
1)s[0],s[1]
2)s[0][0],s[0][1]
3)s[0][0][0],s[0][0][1]
4)s[0~n-1][0][0],s[0~n-1][0][1]
5)s[0][0~n-1][0],s[0][0~n-1][1]
③写完代码后的优化：二维->一个或者两个或者多个一维 一维->常数空间
④通常设 以i为结尾的满足条件的情况为 dp[i];而最终结果在最后一个dp或者所有dp中的最值
⑤动态规划 自上而下 后序递归（reversed[]记录已计算过的答案+越界判断+找到判断+子递归+处理+存reversed[]+返回）
⑥动态规划 自下而上 dp[0]初始值+循环+（满足条件下的）
⑦动态规划转移方程若出现多种情况对应不同转移方程（增减项式），可考虑dp大小+1，多个dp[0]或者dp[0][0]~dp[i][0]/d[0][i],从而统一转移方程
⑧二维遍历写法：
1)已初始化dp[i][i]:00,11,22,33,,,
//确定最终答案是dp[0][size-1]还是dp[size-1][0]还是dp[size-1][size-1]还是全部dp[i][j]中的某个最值。
确定每个数组元素是根据那些数组元素计算得到。从而确定先行还是先列，
确定行从上到下还是从下到上，
确定列从左到右还是从右到左，
只要涉及对对角线临界值则引用上个循环的循环变量
//方法一<==>方法三
for(int j=1;j<size;++j){
for(int i=j-1;i>=0;--i){
dp[i][j]:第一列到队后一列 依次 从对角线上一行到第一行
//方法二<==>方法四
for(int j=1;j<size;++j){//列
for(int i=0;i<j;++i){
dp[i][j]:第一列到队后一列 依次 从第一行到对角线上一行
//方法三
for(int i=size-2;i>=0;--i)
for(int j=i+1;j<size;++j)
dp[i][j]:对角线最后上一行到第一行 依次 从对角线右一列到最后一列
//方法四
for(int i=size-2;i>=0;--i)
for(int j=size-1;j>=i+1;--j)
dp[i][j]:对角线最后上一行到第一行 依次 从最后一列到对角线右一列
(3)递归：
从结果倒推直到问题规模变小，从右到左，99+98+...+1:动态规划相反:相反
①mainFunction+helperFunction
②mainFunction先判断if(!root)情况，如果根节点就是叶子节点时的处理情况和一般情况处理不同 则追加此判断情况的处理;helperFunction只处理if(root)的情况
③一般辅助变量需要从上层/父节点来的则设为传入参数;传入参数设为&形式速度更快,和设全局变量速度相当,不加&会超出时间限制;对应先序
1)参数不会被修改最好设成 const int &x
④需要从下层/子节点来的设为返回值;对应后序
⑤
(4)分治
(去除多余临界点,left,right,mid)：平均，从中间,{1-49}+{50-99},Helper1(int left, int right);Helper2(int left, int right,int mid);
①找到中间分界点,分为 左不含分界点,右不含分界点,含分界点三部分+递归
②左右不含分界点分为 左右空+左右不空情况
③一般优化在于根据分界点分为三个部分时过滤掉无效点,缩小左右不含临界点的范围
(5)回溯+深度优先递归
①
②vector<vector<XXX>>函数返回类/全排列，一般用回溯，即返回结果的所有可能性的情况；一般返回结果所有可能性的情况个数等用动态规划
③分析子树的含义（最好是push和pop一次，而不是可能一次性push pop很多个对象）
④分析每个节点子树个数的限制条件（从第几个子树分支遍历到第几个分支）
⑤结束条件（先判断没找到的条件+再判断找到的条件+后面则需要递归）
⑥回溯框架：
1)全局三个数据结构：res,path,inputArray
2)trackBack三个输入参数：inputArrayIndex(遍历输入数组依据/数组越界依据),findFlag（找到/满足条件依据）,visited（记忆数组）
vector<vector<int>> res;//最终结果存放
vector<int> path;//路径
vector<int> nums;//选择列表
vector<vector<bool>> covered(board.size(),vector<bool>(board[0].size(),false));
//每次思考用covered记录已遍历过的元素时，考虑是否可以在数组置某个值表示已经遍历过，例如board[i][j]=-1 or ‘#’ or ...
void backTrack(辅助变量：vector<vector<bool>> covered(二维网格已走过路径),int a,int b,int c(一维选择列表序号a,二维选择列表序号b,c),int target(遍历找到的条件)):
if(没找到的条件||越界||已covered;a b c，提前剪枝)return;
if(找到的条件&&==;a b c){
res.push_back(path);
return;
}   
visited[]=1;
operator(target);  
for(根据分支条件，遍历选择列表)
path.push_back(XXX);//选择
backtrack(...一般跟i有关...);
path.pop_back();//撤销选择
visited[]=0;
operator(target);
⑦bool backtrack（）类型，注意使用||或运算
1) return backtrack()||backtrack()||backtrack();
2)if(越界条件||已covered条件||...)
(6)linear sweep(线性扫描+排序+O(N))：“双辅战队”
①双指针
1)三指针，一左一右一当前
//[,le)都是0
//[le,cur]都是1
//(cur,ri]未扫描检测
//(ri,]都是2
2)一快一慢，差两倍：
low=0,fast=0;
do{low++,fast+=2;}while(fast!=???||low!=fast);
3)一左一右：++le,--ri;
②滑动窗口
1)unordered_map<char,int>need,windows;//字符出现次数
2)[le,ri)
3)validCount==need.size():覆盖
4)4个问题思考
a.当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
b.什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
c.当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
d.我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
for(char c:p)++need[c];
int sSize=s.size(),pSize=p.size(),nSize=need.size();
int le=0,ri=0;
int validCount=0;
while(ri<sSize){//扩大窗口的条件
char c=s[ri++];//扩大窗口   
if(need.count(c))//更新数据
if(need[c]==++windows[c])
++validCount;            
while(缩小窗口的条件){// if(ri-le==pSize)：固定窗口大小等于pSize，同步前进;while(validCount==nSize):窗口包含p的所有字符时，此时窗口大小>=pSize      
if(validCount==nSize)//找到答案的条件
res.push_back(le);
char c=s[le++];//缩小窗口            
if(need.count(c))//更新数据
if(need[c]==windows[c]--)
--validCount;
}
}
③递增/减栈
1)一般需要两遍,左到右+右到左
2)没有s.clear()函数;        stack<int>().swap(s);    while(s.size())s.pop();
3)for(int i=0;i<nums.size();s.push(i++)){//栈存的是数组下标
while(s.size()&&nums[s.top()]>nums[i])
operate(),s.pop(); 
④单调递增/递减队列
1)duque双向队列，队头为最值  
2)deque<int>d;//存的是数组下标，出现比较<>=时要特别注意写错比较对象
for(int i=0;i<k;++i){//进 滑动窗口前k个 
while(d.size()&&nums[i]>=nums[d.back()])
d.pop_back();
d.push_back(i);
}
res.push_back(nums[d.front()]);
for(int i=k;i<nSize;++i){
if(i-k==d.front())//出 最后一个
d.pop_front();
while(d.size()&&nums[i]>=nums[d.back()])//进最新一个
d.pop_back();
d.push_back(i);
res.push_back(nums[d.front()]);//取最值
}
⑤左右辅助数组left[],right[]
(7)O(longN)：
①二分法
1)前提是有序或者变形有序（旋转有序）
2)两次二分法，一次找a，一次找b  
3)三分法：a=le+(ri-le)/3;b=ri-(ri-le)/3; le~a~b~ri
4)查找左右边界问题：二分查找最后一个/第一个 </<= >/>=的位置
a.先判断是左还是右
b.再判断nums[pos]</<=/>/>=target
0，1，2，3，4，5，6，7，8，9
2，2，2，2，3，3，4，4，6，6
le=0,ri=9;
c.最后一个index使得nums[index]</<=target    
int pos=-1;
while(le<=ri){
int mid=(le+ri)>>1;
if(nums[mid]</<=target)
pos=mid,le=mid+1;
else ri=mid-1;
}
return pos;
d.第一个index使得nums[index]>/>=target
int pos=-1;
while(le<=ri){
int mid=(le+ri)>>1;
if(nums[mid]>/>=target)
pos=mid,ri=mid-1;
else le=mid+1;
}
return pos;
e.应用
for (int i = le; i <=ri; i++)
if (isOK(i))//对应二分查找左边界/第一个满足条件的元素
return i;
->
②线段树
③优先队列priority_queue
1)struct ValKey{
int val;
int key;
ValKey():val(0),key(0){};
ValKey(int v,int k):val(v),key(k){};
bool operator >(const ValKey &vk)const{//greater 
if(val==vk.val)return key>vk.key;
return val>vk.val;
};
/* bool friend operator >(const ValKey &vk1,const ValKey &vk2){//friend不能跟const
return vk1.val>vk2.val;
}*/
bool operator <(const ValKey &vk)const{//less
if(val==vk.val)return key>vk.key;
return val<vk.val;
};
};
2)priority_queue<ValKey, vector<ValKey>, greater<ValKey> > c;
3)struct cmpGreater{  
bool operator()(ListNode *a,ListNode *b){
return a->val > b->val; }//>greater
4)priority_queue<ValKey, vector<ValKey>, cmpGreater > c
(8)Random+Rejection Sampling+Reservoir Sampling
①https://blog.csdn.net/qq_24854861/article/details/105725078
②rand_x(){return 1+rand()%x;}随机生成1~x
③rand_a()+(rand_b()-1)%a可以表示随机1~a*b,记作1~y,即rand_y()
④rand_y()(y>=a)随机表示rand_a()
int k=y/a;
do{int y=rand_y();}while(y>k*a);//拒绝采样
return 1+(y-1)%a;
⑤随机生成浮点数;const double M_PI=3.141592653;
1)random_device rd;//可有可无
2)mt19937 mt;      or     default_random_engine dre;
3)mt=mt19937(rd());      or        dre=default_random_engine(rd());//可有可无
4)uniform_real_distribution<double> randDouble{-1.0,1.0};
5)使用：randDouble(mt)    or randDouble(dre)
⑥累加和/前缀和+二分权重
1)selArray[i]=selArray[i-1]+targetArray[i]
2)int rd=rand()%selArray[selArray.size()-1]
3)while(le<=ri)    if(rd<=selArray[mid])pos=mid,ri=mid-1;else le=mid+1;
⑦二维转一维(一维vector用map替换)+尾指针前移：r行c列 rc=r*c;
1) resVal=selMap.count(rd)?selMap[rd]:sleMap[rd]=rd;
2) selMap[rd]=selMap.count(--rc)?selMap[rc]:rc;
3) res_r=resVal/c;res_c=resVal%c;
⑧蓄水池采样算法：从n（不知道n具体多少）个元素中等概率采样/取出k个元素
1)前k个目标元素入res数组
2)if(rand()%(k+cnt++)<k),则第k+cnt(cnt>=1)个目标元素随机替换res里面一个元素，即k/(k+cnt)概率采样/选择第k+cnt个目标元素入res
3)https://blog.csdn.net/qq_24854861/article/details/105745738
(9)极小化极大：两人玩游戏，一对都对，一错都错
①两人玩游戏，一人先手一人后手交替走，求先手能稳赢的情况（赢，输，平）
②回溯+后序遍历
③player==1:先手,存在一个返回值为true则true,否则false        或运算
④player==0:后手，全部都返回true才true,否则false（存在一个返回值为false)    与运算    
⑤剪枝+记忆化线索
1)alpha beta
2)bitset<N> visited;    +    unordered_map<unsigned long,int>mp;
(10)贪心算法
①动态规划性质+贪心性质：
1)当动态规划需要从0~i个dp[]中选择一个满足条件的最值时，考虑做出那个最有【潜力】，看起来最优的选择即可
2)一般动态规划超时的题目都是用贪心
②[input[i][0],input[i][1]]算出这些区间中最多有几个互不相交的区间==n-最小数里移除区间使剩下区间为无重叠区间==...
1)边界相同算/不算相交：x_end>/>=input[i][0]
2)static bool cmp(vector<int>&a,vector<int>&b){ return a[1]<=b[1];}
3)
sort(points.begin(),points.end(),cmp);
int cnt=1;
for(int i=1,x_end=points[0][1];i<iSize;++i)
if(points[i][0]>x_end){
++cnt;
x_end=points[i][1];
}
return cnt;//return iSize-cnt;
5.代码优化
(1)sort比较函数
①排序对象是自建结构体
1)bool operator  > (...){..};
2)... < ...
3)priority_queue<ValKey, vector<ValKey>, greater<ValKey> > c;
②排序对象是系统自带结构体
1)static bool cmp(...){...};
2)sort(...,cmp);
(2)字符串匹配
①KMP算法:dp[i]表示pattern[0~(i-1)]之间的相同前缀和后缀的长度，pattern[0~(i-1)]本身不算前缀或后缀
string text,pattern;    int i=0,j=-1;    vector<int>dp(pattern.size()+1)    dp[0]=-1;
while(i<pattern.size()){
if(j==-1||pattern[i]==pattern[j])
dp[++i]=++j;
else j=dp[j];}
i = 0, j = 0;     
while (i < text.size() && j < pattern.size()) {          
if(j == -1 || text[i] == pattern[j]) ++i,++j;
else j = dp[j];   
}    
if(j == pattern.size())          
return i-j+1;     
else          
return -1;
②Rabin-Karp算法：哈希映射，共d=256个字符（256进制数），
(3)自动机
class Automaton {
string state = "start";
unordered_map<string, vector<string>> table = {//table [当前状态]->[下一个状态]
{"start", {"start", "signed", "in_number", "end"}},//注意括号位置 
{"signed", {"end", "end", "in_number", "end"}},//vector.size和条件个数有关(0123)
{"in_number", {"end", "end", "in_number", "end"}},
{"end", {"end", "end", "end", "end"}}};
int getIndex(char c) {//输入
if ()) return 0;
else if () return 1;
else if () return 2;
else return 3;
}
public:
void get(char c) {
state = table[state][getIndex(c)];//是(c)不是[c]
if (state == ...) {
...
}
else if (state == ...)
...
else ...
}
};
①使用：Automaton am；
②while(...)am.get(c);
(4)set<vector<int>>res;//unordered_set<>里面的对象不能是vector<int>,最好是简单数据结构
(5)把多数情况的条件语句放在前面，如a,b,出现情况较少的条件放最后else，如c,可大幅度提升执行速度
①while(...)if(a)...else if(b)...else...
②最好按照最可能出现的情况排前面判断
(6)char二维数组->string一位数组
(7)数学函数
①sqrt开平方；log;log10;pow(a,b)几次方；exp e的几次方；ceil向上取整；floor向下取整
②max(v.size(),resMax);//错误    max((int)v.size(),resMax);//正确
(8)int mid = low + (high - low) / 2;比较好
①(high+low)/2容易越界出错
(9)const enum代替define 常量，inline代替define 函数
①类内常量：enum{a,b=0,c=0,d,e};
②const char const * const p;*左所指向数据不可变，*右指针不可变
③const char *&p[5];//从遍历名由内到外分析，p是一个引用，一个指针的引用，一个指向有5个char数据的数组的指针的引用，并且该指向数据不可变
(10)回字符串:反转reverse()
(11)for(int i=0;i<s.size();++i)
ss=ss+s[i]+'#';//ss+=s[i]+'#'会报错！即ss+=s1+s2不可行
①for(auto &i:s) ss=ss+i+'#';    if(s[i]==’#’)...    单个字符不用用”#”
②string s=’a’;报错
(12)if(!root||!root->left&&!root->right)return root;
(13)typedef vector<int>::iterator iter;    iter a=x.begin();
①using iter = vector<int>::iterator;    using iPtr = int*;    typedef int* iPtr;
②using array = int [4];    typedef int array [4];
(14)nullptr可以完全代替指针NULL,但像vector<int> v/vector<TreeNode*>v不是指针不能用nullptr置空,可以用{}置空;
(15)max(a,b);min(a,b);swap(a,b);find(it1,it2,value);lower_bound(it1,it2,value);
(16)for(auto &c:s)  for(auto c:s)    听说&c更高效
①for(auto it=m.begin();it!=m.end();++it)         it->first/second:key/value
②for(auto it:m)    m.first/m.second
③for(auto &a:b)  for(auto &b:c)  b=5; 
1)会直接改变c里面的值,没有&则不会
2)多层auto，除了最内层可&可不&,其他层必须带上&
④for(vector<TreeNode*>::iterator it=v.begin();it!=v.end();++it)被遍历对象不是常用数据结构时不能使用auto
⑤decltype(表达式/函数) it;it的类型和表达式的返回类型一样，但不会计算该表达式/函数
(17)ListNode* head=new ListNode(-1);     ListNode* h=head;        if(h)    h=h->next;
(18)int Nmin=INT_MIN; int Nmax=INT_MAX;
(19)queue<pair<TreeNode*,int> >q;    q.push({root, 1});    q.pop();  pair<int, int> b(1, 2);
①b.first    b.second
②q.push(make_pair(root,1));
(20)
(21)位运算：a=pow(2,x); 乘除a用移位，模a用与运算
①求某个数二进制中1的个数
1)n & (n - 1) 可以消除 n 最后的一个1<<==>>n&(n-1)==0:n是2的幂次方

②位反转:
for(int i=0;i<32;i++)        if(((n>>i)&1) != 0)    tmp |= 1<<(31-i);
③位置1:     temp|= 1<<(n-1);
④位置0:    temp&= ~(1<<(n-1))
⑤取第n位的值:    temp=(temp>>(n-1))&1
⑥异或：不进位加法，同为0异为1; 与+左移1位：进位;
⑦2^N时间复杂度/子集：bitSet=1<<nums.size(); for(int i=0;i<bitSet;++i)
0~2^(nums.size()-1) i的第j位为0表示不选择，1反之
(22)链表：
①伪头+释放节点
1)LinkNode* LN=new LinkNode(0);    LN->next=head;    
2)LinkNode *pre=LN/nullptr,*cur=head,*next=nullptr,*toDelete=nullptr;
3)...while(cur){next=cur->next;cur->next=pre;pre=cur;cur=next;}...
4)...if(toDelete){delete toDelete,toDelete=nullptr;}...
5)toDelete=LN,LN=LN->next;
6)delete toDelete;
7)return LN    ;
②快慢指针：
1)前后差两倍速度slow=head;fast=head or fast=head->next;
if(!head||head->next==head)return head;
if(!head->next)return nullptr;
ListNode *low=head,*fast=head;
do{
low=low->next,fast=fast->next->next;
}while(fast&&fast->next&&low!=fast);
if(!fast||!fast->next)return nullptr;
fast=head;
while(low!=fast)
low=low->next, fast=fast->next;
return low;
2)前后差固定值n
③swap也可以交换结构体指针，swap(ListNode1,ListNode2)
(23)考虑元素为空或者为1的特殊情况if(！head||！head->next)return head;
(24)数组下标差值范围限定+对应数组差值范围限定：|n[j]-n[i]|<=a&&|j-i|<=b
①滑动窗口+map/set(有序)+lower_bound
②auto x=s.lower_bound(n[j]-a);    //n[i]-a<=n[j]
③x!=s.end()&&*x<=n[j]+a            //n[j]<=n[i]+a
④if(s.size()==b+1)s.erase(n[j-b]);
(25)1<=x<=26:滑动窗口
(26)二叉树遍历
①层序遍历
1)1
if(!root)return nullptr;
queue<TreeNode*> q;    q.push(root);
while(q.size()){
int size=q.size();
while(size--){
TreeNode* p=q.front();    q.pop();    
//处理节点
if(p->left)q.push(p->left);
if(p->right)q.push(p->right);
}
}
2)2
if(!root)return nullptr;
queue<TreeNode*> q;    q.push(root);
while(q.size()){
int size=q.size();
while(size--){
TreeNode* p=q.front();    q.pop();    
if(p){
//处理节点
q.push(p->left);
q.push(p->right);
}
}
}
3)3

②morris二叉树遍历:时间复杂度O(n),空间复杂度O(1)
1)记忆口诀:循环当前,左右到底,右子有无,当前左右,后前前中
后左尾头,右子反转,next开头,首尾相接,遍历反转
2) morris遍历时，此时若还有线索未解锁则不能直接返回函数，否则报错
3)前中后代码框架
TreeNode *cur=root,*temp=nullptr;
while(cur){
temp=cur->left;
if(temp){
while(temp->right&&temp->right!=cur)
temp=temp->right;
if(temp->right){
temp->right=nullptr;
//后序节点处理
}
else{
temp->right=cur;
//前序节点处理
cur=cur->left;
continue;
}           
}
else
//前序节点处理
//中序节点处理
cur=cur->right;
}
4)中序
void InOrder(TreeNode* root){//morris中序（左，根，右）
TreeNode *cur=root,*pre=nullptr,*temp=nullptr;
while(cur){
temp=cur->left;
if(temp){
while(temp->right&&temp->right!=cur)
temp=temp->right;
if(temp->right)
temp->right=nullptr;
else{
temp->right=cur;
cur=cur->left;
continue;
}
}
operate(cur),pre=cur;//如果需要用到前驱节点则需定义pre,否则不用
cur=cur->right;
}
}
5)前序
void PreOrder(TreeNode* root){//morris前序（根，左，右）
TreeNode *cur=root,*pre=nullptr,*temp=nullptr;
while(cur){
temp=cur->left;
if(temp){
while(temp->right&&temp->right!=cur)
temp=temp->right;
if(temp->right)
temp->right=nullptr;
else{
temp->right=cur;
operate(cur),pre=cur;//如果需要用到前驱节点则需定义pre,否则不用
cur=cur->left;
continue;
}
}
else
operate(cur),pre=cur;//如果需要用到前驱节点则需定义pre,否则不用
cur=cur->right;
}
}
6)后序
void PostOrder(TreeNode* root){//morris前序（左，右, 根）
TreeNode *cur=root,*pre=nullptr,*temp=nullptr;
while(cur){
temp=cur->left;
if(temp){
while(temp->right&&temp->right!=cur)
temp=temp->right;
if(temp->right){
temp->right=nullptr;
PostHelper(cur->left);
}
else{
temp->right=cur;
cur=cur->left;
continue;
}
}     
cur=cur->right;
}
operate(head)
}

void PostHelper(TreeNode* root){
//1 链表（右）逆序，头节点为root
TreeNode *cur=root,*pre=nullptr,*next=nullptr;
while(cur){//next开头,首位相接,方便记忆,如下
next=cur->right;//next=cur->right=pre=cur=next
cur->right=pre;
pre=cur;
cur=next;
}
//2 右边界逆序遍历
cur=pre;//此时头节点为pre
while(cur){
operate(cur);
cur=cur->right;
}
//3 链表（右）逆序，头节点为pre
cur=pre,pre=nullptr,next=nullptr;
while(cur){
next=cur->right;
cur->right=pre;
pre=cur;
cur=next;
}
}
③迭代遍历
1)记忆口诀
当前有栈,循环入当,左t右p,p后取值,中反tp,后反左右,后右空前
2)前序框架(中后序都有此推导记忆)        
void preorder(TreeNode* root) {
stack<TreeNode*> S;
TreeNode* cur = root;
while(cur || S.size()){
while(cur){
S.push(cur);
operate(cur->val);//                
cur=cur->left;
}
cur=S.top();            
cur=cur->right;//
S.pop();//
}      
}
void preorder(TreeNode* root) {
if(!root)return;
stack<TreeNode*> S;
TreeNode* cur = root;
S.push(cur);
while(S.size()){
cur=S.top();
S.pop();
...
if(cur->left)S.push(cur->left);
if(cur->right)S.push(cur->right);
}    
}  
void preorder(TreeNode* root) {
if(!root)return;
stack<TreeNode*> S;
TreeNode* cur = root;
S.push(cur);
while(S.size()){
cur=S.top();
S.pop();
if(cur){
...
S.push(cur->left);
S.push(cur->right);
}
}    
}  
void preorder(TreeNode* r1,TreeNode* t2) {
if(!t1)return t2;
else if(!t2)return t1;
stack<pair<TreeNode*,TreeNode*> > s;
pair<TreeNode*,TreeNode*> cur={t1,t2};
s.push(cur);
while(s.size()){
cur=s.top(),s.pop();
//处理节点            
if(cur.first->left||cur.second->left){
if(!cur.first->left&&cur.second->left)
cur.first->left=new TreeNode(0);
else if(cur.first->left&&!cur.second->left)
cur.second->left=new TreeNode(0);             
s.push(pair{cur.first->left,cur.second->left});
}             
if(cur.first->right||cur.second->right){
if(!cur.first->right&&cur.second->right)
cur.first->right=new TreeNode(0);
else if(cur.first->right&&!cur.second->right)
cur.second->right=new TreeNode(0);             
s.push(pair{cur.first->right,cur.second->right});
}               
}
}  

3)中序        
void inorder(TreeNode* root) {
stack<TreeNode*> S;
TreeNode* cur = root;
while(cur || S.size()){
while(cur){
S.push(cur);                
cur=cur->left;
}
cur=S.top();
S.pop();//
operate(cur->val);//
cur=cur->right;//
}      
}     
4)后序1    
void postorder1(TreeNode* root) {
stack<TreeNode*> S;
TreeNode* cur = root;
vector<int> v;
while(cur || S.size()){
while(cur){
S.push(cur);
v.push_back(cur->val);//            
cur=cur->right;//
}
cur=S.top();            
cur=cur->left;//
S.pop();
}   
reverse(v.begin(),v.end());//
opreate(v);//
}
5)后序2
void postorder(TreeNode* root) {
stack<TreeNode*> S;
TreeNode* cur = root,*pre=nullptr;
while(cur || S.size()){
while(cur){
S.push(cur);
operate(cur->val);//                
cur=cur->left;
}
cur=S.top();    
if(cur->right==nullptr||cur->right==pre){//
S.pop();
operate(cur->val);
pre=cur;
cur=nullptr;
}
else    
cur=cur->right;//            
}      
}
(27)序列化二叉树为某序的字符串
①层序
TreeNode* cur=root;
queue<TreeNode*> q;
q.push(cur);
while(q.size()){
int qs=q.size();
while(qs--){
cur=q.front(),q.pop();    
if(cur){
res+=to_string(cur->val)+",";
q.push(cur->left),q.push(cur->right);
}
else     res+="#,";          
}
}
②前中后
string serialize(TreeNode* root) {
if (root == NULL)
return "#";
return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right) + ",";
}
(28)递归转迭代循环的通用方法

(29)两栈实现队列：一出队列栈，一入队列栈
(30)两队列实现栈+一队列实现栈
①指针交换而不是整个队列拷贝：swap(q1,q2);
②每次进栈都循环移位队列
(31)（运算符优先级):等不等于（==/!=）>按位运算（& | ^ ~）>与或条件判断（&& ||）
return num>0&&num&0x55555555==num&&num&(num-1)==0;
①位运算 i<<1 等效于 i/2  (i<<1)|1 等效于  i/2+1
(32)log(exp(n))    log10(n)        
①double x=log10(a)/log10(b);         x==int(x)?整数：非整数;
②用log(n)，以e为底容易错，小数太多
(33)size() 目前容器正拥有的元素个数
capacity() 容器能储存的元素个数，即容量
reserve() 重新指定容器能存储数据的个数
resize() 重新指定容器有效的元素个数
设元素原本的v.size()是n 当调用v.resize(m)后，有两种情况：
1.若 m < n ,则只保存容器前m个元素
2.若m > n ，则容器之前储存的n个元素不变，不足m的部分补0
调用v.resize(m,val)将不足的部分用val填充
(34)交换数组元素
vector<int> XXX(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) 
return XXX(nums2, nums1);
...
}
(35)连续元素和为k的子数组个数:
①map[累计和sum]++;
②count=map.find(sum-k)!=map.end()?count+map[sum-k]:count;
(36)注意有无符号左移不一样情况:int a;    a=unsigned(a)<<1;
(37)//平方 pow()    int a = pow(4,2);// 4的平方=16
//开方    int b = pow(4,0.5);// 4的平方根=2    int c = sqrt(4);// 4的平方根=2
//整数绝对值int c = abs(b-c);     //浮点数绝对值double d = fabs(b-c);
(38)审题:abcaaaaaaa
①字串/子字符串:必须是连续的,abc是,aa不是
②子序列:顺序取出,不一定是连续的,aa是,
(39)线段树=leIndex+riIndex+leftPtr+rightPtr
https://blog.csdn.net/qq_24854861/article/details/105306753

(40)并查集：处理复杂DFS问题 一维O(N) 二维O(MN)
①二维，注意并查的对象：网格坐标还是网格点坐标
②初始化+查找+合并+是否连通+集合个数+元素个数
③父节点+秩+元素+集合：“父子圆寂”
④特征
1)自反：x和x是连通的
2)对称性：(x,y)是连通的，则(y,x)也是连通的
3)传递性：(x,y),(y,z)是连通的，则(x,z)是连通的
⑤套用模板后，真正自己要做的事是遍历找出两个元素要合并的条件，然后进行合并即可
class UnionFind{
vector<int>parent,rank,size;//指向父节点，秩/高度，该集合里的元素个数
int cnt;//集合个数
unordered_map<int,list<int>>traversChild;//遍历该集合内的元素
public:
UnionFind(vector<vector<char>>& board){
int m=board.size(),n=board[0].size();
cnt=m*n;
parent.resize(cnt);
rank.resize(cnt,1);
size.resize(cnt,1);
for(int i=0;i<cnt;++i)
parent[i]=i,traverseChild[i].push_back(i);        
}
UnionFind(int n){
cnt=n;
parent.resize(n);
rank.resize(n,1);
size.resize(cnt,1);
for(int i=0;i<n;++i)
parent[i]=i,traverseChild[i].push_back(i);  
}
int Find(int x){
return x==parent[x]?x:(parent[x]=Find(parent[x]));
}
void Union(int a,int b){
int fa=Find(a),fb=Find(b);
if(fa==fb)return;
if(rank[fa]>rank[fb]){
parent[fb]=fa;            
size[fa]+=size[fb];
//traverseChild[fa].splice(traverseChild[fa].end(),traverseChild[fb]);//无序
traverseChild[fa].merge(traverseChild[fb]);//默认升序
traverseChild.erase(fb);
}
else if(rank[fa]<rank[fb]){
parent[fa]=fb;
size[fb]+=size[fa]; 
traverseChild[fb].merge(traverseChild[fa]);  
traverseChild.erase(fb);         
}
else{
parent[fa]=fb;
size[fb]+=size[fa];
++rank[fb];
traverseChild[fb].merge(traverseChild[fa]);
traverseChild.erase(fb);
}
--cnt;
}
list<int> getTraverse(int x){
int fa=Find(x);
return traverseChild[fa];
}
bool isConnected(int a,int b){
int fa=Find(a),fb=Find(b);
return fa==fb;
}
int getCnt(){
return cnt;
}
int getSize(int x){
return size[Find(x)];
}
};
(41)拓扑排序(一维存入度，二维存出度，队列遍历0入度节点)
①https://blog.csdn.net/qq_24854861/article/details/105441337
(42)排序：冒选插    快堆归希    计基桶
①https://blog.csdn.net/qq_24854861/article/details/105466059