1.构造二叉树前中与后中
1.105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
分析前序和中序会发现，单看前序一定能确立根，单看中序一定能确立左右子树，既然这样，那我们就可以利用这一点确定一颗二叉树了。我们使用这一点递归建立二叉树.。既然是构造二叉树，那首先确定一点就是一定要动态开辟节点，其次我们要确立的是如何根据中序建立左右子树。
如上图分析，发现复原这颗二叉树，就是不断用前序确定根节点，中序确定左右子树，那如何构建 前序与中序的关系呢？就是用下标，题目给的是两个顺序表，不难想到应该是要使用下标建立关系的。根据上图分析，我们还可以得出构建二叉树的顺序是前序遍历的顺序，根再左子树，最后才右子树。这一点很重要，这就是我们递归的一个重点。
入上图分析，我们得出是要使用前序数组的根节点的下标来标识中序数组的的根节点，从而递归确立中序数组的每一个根节点，构建二叉树。构建顺序是前序遍历的顺序，那我们不难得出下标建立的递归表达式。
最后一个分析就是，递归终止条件，什么时候终止递归呢？使用空指针吗？这里还再构建，咋用空指针呢？一样使用的是下标，区间内嘛，如果左下标大于右下标，那他一定是不存在的。
还有一个比较容易想错的就是，这里是递归，如果想实现遍历的效果，那这个参数要是引用传参，否则局部变量是无法实现的，这点要想通。
代码
TreeNode* _build(vector<int>& preorder, vector<int>& inorder,
int& prei,int inbegin,int inend)
{
if(inbegin > inend ) return nullptr;
TreeNode* root = new TreeNode(preorder[prei]);
int rooti = inbegin;
while(rooti < inend)
{
if(inorder[rooti] == preorder[prei]) break;
rooti++;
}
prei++;
root->left = _build(preorder,inorder,prei,inbegin,rooti-1);
root->right = _build(preorder,inorder,prei,rooti+1,inend);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
int prei = 0,inbegin = 0,inend = inorder.size()-1;
TreeNode* root = _build(preorder,inorder,prei,inbegin,inend);
return root;
}错误点
其实来说这道题目，错误点还是比较少的，只要分析对了，还是很难写错的。这里列举下我自己写题烦的一个错误点，栈溢出
这里出现栈溢出，大概就是你的递归条件出问题了，我就是忘写递归条件了。
2.106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）
刚刚分析完前序和中序构造二叉树，那其实中序和后序构造二叉树是一样的。思路都没变，很类似。分析中序和后序特点，得出后序确定根，中序确定左右子树，这与上到题目区别不大。但是，这里的构造顺序就不一样了，后序是先左子树，再右子树，最后才根，既然我们是从后序数组的根节点小标来表示中序数组根节点的下标，那我们确定了一点就是，第一个建立的结点肯定是根节点，因此，我们构造顺序应该是先构造右子树再构造左子树，这才能正确构造二叉树。这是与上道题目差异比较大的，其次就是下标的关系了吗。既然都是从后遍历后序数组，那传参的时候，要注意，是size-1不是0了。
上道题目分析画图已经很详细了，这道题与上道题极度相似，就不做画图分析了。
代码
TreeNode* _build(vector<int>& inorder, vector<int>& postorder,
int& posti,int inbegin,int inend)
{
if(inbegin > inend) return nullptr;
TreeNode* root = new TreeNode(postorder[posti]);
int rooti = inbegin;
while(rooti != inend)
{
if(postorder[posti] == inorder[rooti]) break;
rooti++;
}
posti--;
root->right = _build(inorder,postorder,posti,rooti+1,inend);
root->left = _build(inorder,postorder,posti,inbegin,rooti-1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{
int posti = postorder.size()-1,inbegin = 0,inend = inorder.size()-1;
TreeNode* root = _build(inorder,postorder,posti,inbegin,inend);
return root;
}错误点
这道题目注意是从后遍历后序数组，所以下标是--，不是++，还有的话就是注意传参吧，这里参数比较多，不要传错，我写这道题的时候，就没看清传错了，查了一会才查出来。
总结
上面两道题的思路类似，属于很经典的二叉树题目，建议必须掌握
2.二叉搜索树与双向链表_牛客题霸_牛客网
我个人感觉这道题，第一次看到好难，写这种题，都感觉头疼。但是分析下其实还是可以的写的。这道题要求我们是中序还原双向链表，头疼的就是这是个双向链表，不仅要链接next还要链接prev，链接一个还好说，但是链接两个真的头疼。而且这道题目要求空间复杂度O(1)，时间复杂度为O(n)，那就只能是原树上遍历一遍就构建好，这让你一点投机取巧的办法都没有了。回归正题，我们分析一下，这道题是中序遍历的时候建立双向链表，既然是中序遍历，那我们就用递归的方式实现
如上图分析，我们需要一个prev指针记录上一个遍历的结点，才能实现链接next。
根据递归展开图，我们发现他是在归的时候才实现链接的。
代码
void InOrder(TreeNode* cur,TreeNode*& prev)
{
if(cur == nullptr) return;
InOrder(cur->left,prev);
cur->left = prev;
if(prev) prev->right = cur;
prev = cur;
InOrder(cur->right,prev);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
TreeNode* prev = nullptr,*head = pRootOfTree;
InOrder(head,prev);
while(head && head->left)
{
head = head->left;
}
return head;
}关键点
关于这道题，首先出发的点就是中序遍历，题目暗示我们就是要改变链接关系，不可以使用其他方法实现，因此我们接下来就是从如何改变链接关系的点思考，既然是双向链表，那肯定是要一个prev结点来记录上一个遍历的结点，这样我们才能实现上一个结点与下一个结点的链接。如果想明白了这里，那应该就很简单了。
注意点
我们这里返回的是一个头节点，虽然我们改变了链接关系，可是头节点还是二叉树的根节点，不是链表的头节点，所以还需要更改下这里的头节点。
错误点
这里我再次写这道题目的时候发现一个很有意思的错误点，超出内存限制。
对于递归的题目，超出内存限制，那就是递归过深了。
问题就出在下面这段代码
画一下上面的递归展开图你会发现，这里的结点成环了，那这不久一直递归了吗？那这是啥原因呢？我们分析下出错的代码，他是在没有链接完就赋值prev了，这是不正确的，从第一个结点分析，他的prev就应该是nullptr，按照出错的代码，链接一半prev就指向自己了，这肯定出错呀。按照逻辑分析，也应该是，先链接完，在赋值。这和链表的链接是一个原理的。