算法题各题型思路总结¶
链表总结¶
1.分隔链表（假设分隔值为x）可以定义两个链表，一个连接比x大的，一个连接剩下的，这种方式最后注意连接起来的时候，大的那个链表末尾要置空，防止头尾相连，小的连上大的，定义哑节点操作更方便。这个问题也可以通过定义两个数组来做，各自存放，最后在把小的先放入链表中，大的后放入。
2.合并有序链表通过递归来做，先对比两个表的表头，如果是从大到小排序，则只需要让表头值较小的链表的第二个节点开始与另一个链表进行递归。
3.两数相加链表逆序排列问题，定义一个进制即可，注意取余操作和进制的取整操作，并且在最后一位加完后，还要对进制进行一次判断，若大于1，需要再定义一个空间存放该值。
4.反转链表，旋转链表（可能多用到取余决定位置下标）问题，如果需要剪断的可以通过快慢指针或者对值比较或者其他方式找到剪断的位置，然后进行置空操作，进行翻转只要率先定义一个空节点和当前节点的next节点即可，最后在接回原来的链表中，注意指针的指向可能因为逆序发生了改变，画个图就好理解了。
5.两两交换链表，利用递归就好了，和合并链表同理。
6.删除倒数第k个直接快慢指针，快指针先运行k步。
7.将一个数组有序合并到另一个有序数组中，可以从最大值开始比较，将大的放入数组的末尾，这样既不会影响存储，也不会影响前面的值的比较。
8.寻找两个链表第一个公共节点时，先把较长的链表剪断到和两一个链表一样长，然后逐一比较他们的值，第一个相等的即是所求的。
9.对链表进行插入排序，只要定义两个指向头结点的指针，一个每次都指向当前要比较元素的位置，一个只想之前已经排序完的最后一个元素的位置，若当前的比排序完的最后一个节点的值大，继续往下即可，若小了，则需要在定义一个指针指向头节点，然后遍历找到比当前节点小的最大值，然后插入在她的后面。
10.重排链表，需要先利用快慢指针找到中间值，然后剪断，将后半部分在进行逆序，然后一次插入到前排，注意指针指向问题。
11.删除当前所在位置的节点，把后一个节点的值赋给当前节点，在直接让当前节点的指针指向下下个节点。
二叉树总结¶
1.给定一个有序链表，建立平衡二叉搜索树，我们要先用快慢指针获取到链表的中间节点，然后建立一个树节点，把树节点的值赋为中间节点的值，然后递归左右子树（有序链表那么我们找中间值就通过快慢指针来实现，快指针一次走两个next，慢指针一次，，然后定义建立函数，每次找到中间作为当前节点，左节点是他左边部分的中间值，右节点是他右边部分的中间值，遍历。）
2.二叉树展开为链表，需要现已知递归到最下面，然后从底往上，（比如说链表一直朝右）如果没有左子树，则继续往上回溯，如果有左子树，没有右子树，直接把左子树变成右子树即可，如果有左子树，就需要（由前面的便利可以确定该左子树本身一定没有左子树了）遍历到当前左子树的最右节点，然后把当前根的右子树接上去，再把整个左子树变成当前根的右子树，然后把左子树置空，在继续往上回溯，即可。
3.二叉树的中序遍历用栈的话先把根节点和全部的左节点都放进去，放完以后，在开始出栈，每出一个就把他的值存进数组里，同时遍历他的右子树。（先存后取）
4.二叉树的前序遍历用栈把根节点先入队，然后while循环，把当前节点的右节点先入队，然后左节点入队，每次取栈顶节点，都把他放入数组中。（边取边存）
5.二叉树的后续遍历还是按照前序遍历那样，不过先让左边的节点进，然后让右边的进，这样得到的数值里面的节点顺序就是根右左，然后再反转数组，得到左右根。
6.N插树的前序便利和后序遍历与二叉树一个做法，就是左右节点入栈会通过for循环来入，注意区分先后就可以了。
7.二叉树的层序遍历，如果正常的从上往下，从左往右（或从右往左），只要一个队列和一个数组即可完成了，每次左先进右后进（或者反）；如果说是从下往上，从左往右（或者从右往左）的话，就需要借助栈和队列同时来完成，每次右边先进队列，然后出队列进栈，然后再操作左边，最后进行出栈，这样得到的是从左往右的。如果说需要逐行输出的话，就定义一个二维数组，然后定义一个n=rear-front；如果需要从下往上逐行返回，只要把从上往下的数组的行给逆转即可，列不用动。
8.节点值是1到n的不同种类的二叉搜索树的个数为G(n)=G(i−1)⋅G(n−i)（i从1到n累加）笛卡尔积的形式(G(0)=G(1)=1);
9.判断一棵二叉搜索树是否合理，只要中序遍历，然后遍历数组即可，如果是个值从小到大的，即符合。
10.判断两棵树是否相等，考虑两棵树都为空，则相等，只有一颗为空，则不等，当前值不相等，则不等，否则返回左右子树的递归（&&）。
11.判断一颗二叉树是否是对称二叉树，把他拆掉分作左子树和右子树两个树，然后像第九条那样直接比较就好了，不过一个向左，一个向右。
12.通过前序遍历中序遍历（或者中序遍历后序遍历）建立二叉树，先建立下根节点，然后在中序遍历中找到他所在的位置，然后定义出左右子树的前中遍历的区间，在递归左右子树即可。
13.判断是否是平衡二叉树时，在heigh函数中，要返回 return fmax(height(root->left),height(root->right))+1;在isbalanced函数中我们要返回 return fabs(height(root->left)-height(root->right)) <=1&&isBalanced(root->left)&&isBalanced(root->right)。
14.计算二叉树的最小深度，分情况讨论，当左子树存在，右子树不存在时，leftdepth+1，当左子树不存在，右子树存在时，rightdepth+1，当左右子树都存在时，返会fmin+1.
15.求路径综合是否存在给定的目标值问题，每次遍历都会减掉节点上的值，当遍历到叶子节点时，如果count等于0，就说明存在该路径，判断的过程分四种，左右子树都不存在且count为0，则符合，如果都不存在但count不为0，则不符合，如果左子树存在并且递归左子树，如果最后的递归结果满足第一种情况就会返回ture，右子树同理，如果都不满足，最后false。
16.关于二叉树总和等于目标值的路径问题，如果说不符合条件，就把当前的值放入数组path中，如果说是叶子节点了，并且值也符合每次被剪掉当前的target，则将该叶子节点放入path中，并且开设新的数组，把path的值放进去，因为在总和不为target的情况下需要返回一个空数组。
17.根节点到叶子结点的总和（例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123），用sum = sum*10+root->val来表示求和，当左右子树都为空时则返回sum，否则返回 return dfs(root->right,sum) + dfs(root->left,sum)；
18.翻转二叉树（每一个左右二叉树的分支都左右交换），只需要借助一个temp变量，交换，然会递归左右子树就可以了。
19.二叉搜索树，找公共祖先，可以利用二叉搜索树的特性，如果当前节点同时大于两个目标节点，则公共祖先必定在当前结点的左子树中，如果同时小于，则在右子树中，否则的话就是一大一小，他就是公共祖先。
20.关于普通二叉树的祖先问题，如果遍历到的当前节点等于p或者q，或者null，则直接返回当前节点，否则返回null，如果左右子树都存在就返回当前节点，如果只存在左子树就返回左子树，如果只存在右子树就返回右子树，对于是否是p，q，null的判断要放在递归的前面。（没有二叉搜索树的性质，那么找祖先，就用自底向上的遍历方式，即后序遍历，如果找到的节点是p，或者q的话就返回，然后一层层回溯）。
21.求树的所有左叶子之和，只要判断一个节点的左节点存在，并且该左节点的左右节点都不存在，则该节点为左叶子节点，把它加到sum里面去，然后遍历左右子树，返回left + right + sum
22.关于删除二叉树中节点值操作，当值等于key时一共分四种情况，前面三中比较简单，左右子树都不存在，只有左存在，只有右存在，最后一种要么找左子树的最右节点，要么找右子树的最左节点，找到以后把该节点的值赋值给要删除的节点，然后把该节点删除掉；然后再看大于key递归左子树，小于递归右子树。
23.关于二叉搜索树中的众数，定义一个前驱节点，如果前驱节点与当前节点相同，count就++，不同，就回到1，因为是二叉搜索树同样大的数是连在一块的的，如果和当前的最大众数一样就把他输入，如果遇到比当前最大众数更大的，就把数组清空重新存储
24.输出树的最左边的节点，很简单，直接用层序遍历，反着装，先让右子树入队，再让左子树入队，最后出去的就是最左节点。
25.关于找二叉搜索树的差的绝对值的最小值，可以先中序遍历一遍，存入数组里面，然后数组中每一位两两比较，二叉搜索树差的绝对值最小值必定是相邻的两个，也可以一边中序遍历一边比较，通过定义一个前驱节点，每当在本次比较完后，就把当前的cur赋值给pre，然后让右子树入栈，再进入下一次比较。
26.二叉搜索树的值改为比他大的以及等于它的值的和，需要先递归到右子树的最右节点，因为该节点是最大的，改完以后还是它本身，然后把他的值赋给pre，上面每往上一层，就加上pre的值，然后把自己的值赋给pre，给上一层继续加，最后在递归右子树。
27.求二叉树的最大直径（及任意两个节点相隔长度的最大值），直接递归左右子树，返回fmax（left，right）+1，同时每次比较max和left+right的最大值。
28.构建最大二叉树（给定一个数组，把最大的点做为根节点，该点左边为左子树，右边为右子树），直接for找出最大值，创建节点，赋值给他，递归左右子树。
29.将两棵树的节点，重叠起来，新建一棵树，遍历两棵树，如果一个节点为空，直接返回另一个，如果都不为空，新建一个节点，把他们的值的和赋值过来，然后递归左右子树。
30.修建二叉搜索树（给定一个区间，不在区间内的节点删除掉），如果某一点小于下界，直接 root = root->right;然后， root = trimBST(root, low, high);找到符合条件的值，如果大于上界，操作类似，如果不满足这两个情况，即在区间内，递归左右子树。