1.669. 修剪二叉搜索树（难）：递归法，当当前节点的值小于区间最小值，就遍历其右子树（左子树肯定都不符合条件，可以完全放弃了），直到返回符合条件的结点作为当前根节点（大于区间最大值时同理）。然后再继续处理下一层，即对它的左右结点分别作为根节点进行递归，最后将处理后得到的结果作为左右子节点返回给当前根节点。2.108.将有序数组转换为二叉搜索树：要求是平衡二叉搜索树，所以取数组中间值作为根节点，然后进行分割。再递归获取左右子树的根节点（根据分割点生成相对应的左右子树的区间）。3.538.把二叉搜索树转换为累加树：题目要求把当前结点与比它大的值都做一个相加操作。采用递归右中左遍历（结点值是倒序的），双指针执行相加操作。文本查询项目终于搞清楚了各个类之间的关系，以及函数调用的过程。但还是有点懵懵的，等后面学了面向对象的设计应该会有更深的理解。

1.235.二叉搜索树的最近公共祖先：递归法：利用二叉搜索树的特性，如果遇到的结点是第一次出现在[p,q]区间中的，那么这个结点一定是最近公共祖先，pq分别出现在这个结点的左右子树中，由这个结点分化出来的任何结点尽管值在[p,q]区间，但是它们都不是公共祖先。2.701.二叉搜索树中的插入操作：不考虑改变树结构的方法，只将其加入到树最后的空结点处。利用搜索树的特性，找到要插入结点的空结点处，并让此时的root->left/root->right等于新new出来的结点。3.450.删除二叉搜索树中的节点：//递归，多种情况分析        //1.没找到待删除结点，遍历到空结点,直接返回        if(root == NULL) return root;        //找到待删除结点 if(root->val == key){            //2.待删除结点为叶子结点，直接删除该节点，并返回空结点 if(root->left == NULL && root->right == NULL){                delete root;                return NULL;            }            //3.待删除结点左孩子为空，右孩子不为空，右孩子补位，并返回 else if(root->left == NULL){ TreeNode* node = root->right;                delete root;                return node;            }            //4.待删除结点右孩子为空，左孩子不为空，左孩子补位，并返回 else if(root->right == NULL){ TreeNode* node = root->left;                delete root;                return node;            }            //5.待删除结点左右孩子都不为空，            //则将待删除节点的左子树放到待删除节点的右子树的最左面节点的左孩子的位置            //并返回删除节点右孩子为新的根节点。            else{ TreeNode* cur = root->right; while(cur->left){ cur = cur->left;                 }//找到右子树最左边结点的孩子位置 cur->left = root->left;                TreeNode* tmp = root; root = root->right;                delete tmp;                return root;            }        } if(root->val > key) root->left = deleteNode(root->left, key); if(root->val right = deleteNode(root->right, key);        return root;

1.530.二叉搜索树的最小绝对差：依然是利用二叉搜索树中序遍历得到的结点是有序的特性，对其进行递归中序遍历，并采用双指针法得到两个结点间的绝对差（中序遍历得到的有序数组中相邻两个结点间的绝对差一定是最小的，不需要再去与更远的结点进行比较，只需要比较两两相邻间的差值就够了），最后通过对绝对差进行不断更新就能获得最小绝对差。2.501.二叉搜索树中的众数： 递归中序遍历，双指针比较前后两个结点是否相等，同时更新maxValue，当count==maxValue时，将该元素加入到结果集中。如果count>maxValue，要注意更新maxValue的值，并清空结果集（失效）。注意递归过程中这些值都要是全局变量。3.236.二叉树的最近公共祖先：递归后序遍历，        //左右子树都不为空，说明找到了pq，此时root就是最近公共祖先        if(left != NULL && right != NULL) return root;        //当一边找了了p/q，就直接返回这边的结点，        //当层层递归结束，要么会只返回这个结点（这个结点本身就是最近公共祖先）        //要么会与另外一支汇合，分别作为左右结点返回值，最后返回他们此时的根节点        if(left != NULL && right == NULL) return left;        else if(left == NULL && right != NULL) return right;        else return NULL;这两天被文本查询卡住了，有点烦躁，把权游八季的解说看完了，现在心静下来了，后面继续刷算法，搞完这个文本查询就开始学STL了。不要放弃！

1.654.最大二叉树：递归前序遍历，找到最大值作为根节点后，再分别将其左右的数组区间作为新的数组传入递归函数，返回值作为其左右结点。2.617.合并二叉树：采用递归前序的方法合并两棵树。3.700.二叉搜索树中的搜索：迭代法，二叉搜索树的特性指明了遍历方向。4.98.验证二叉搜索树：验证二叉搜索树关键是理解二叉搜索树中序遍历得到的数组是有序（单调递增）的数组。可以不用建立一个数组来获取遍历结果再去进行比较，而是直接通过双指针法（进入下次递归前pre指针保存上一个结点的指针）进行比较。

1.513.找树左下角的值：树的最后一行的最左边的值。用层序遍历（队列）最好理解，只要记录最后一层的第一个元素即可。result设为全局变量，采用for循环控制条件只记录i=0时的值。2.112. 路径总和：判断树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。递归法，遍历过程中直接对目标值进行更改，出口就是找到了叶子节点且目标值被减到0了，就true，否则false。里面其实涉及了回溯的过程，直接将每次遍历某个结点，目标值被修改后的值直接作为参数进行下一轮递归（由于每次递归调用都有它自己的 targetSum 副本（基于调用时的上下文），当递归返回时，上一层递归的 targetSum 仍然是它调用子递归之前的值（因为函数调用栈的帧被弹出，局部变量也随之销毁）），所以相当于是隐式地回溯了targetSum的值。值得注意的是，在257. 二叉树的所有路径那道题中，参数是一个容器（如 std::vector），情况就不同了。容器是按引用或指针传递的，或者更常见的是，我们直接传递容器的引用或指针以避免不必要的拷贝。在这种情况下，对容器的修改会影响到所有引用该容器的函数或对象。因此，在递归函数中处理容器时，我们需要显式地进行回溯，以确保在递归调用返回后，容器恢复到正确的状态。这通常是通过在递归调用之后从容器中移除添加的元素来实现的。总结来说，当我们按值传递基本数据类型（如 int）时，递归调用自然地提供了回溯的效果，因为每个递归层都有自己的参数副本。但是，当我们传递容器或对象时，这些数据结构通常是在多个递归层之间共享的，因此我们需要显式地进行回溯来维护它们的状态。3.106.从中序与后序遍历序列构造二叉树：递归法对中序和后序数组进行切割，然后再去递归找到每一个子树的根节点左右节点。        //1.判断后序数组为空，则root为空结点        //2.将后序数组最后一个元素设为根节点        //3.根据根节点的值寻找中序数组中根节点的位置（for循环，得到位置下标就break），作为切割点        //4.切割中序数组，得到左中序、右中序两段数组        //5.切割后序数组，得到左后序、右后序两段数组        //6.递归处理左子树（将切割出来的左中序、左后序作为参数）、右子树（将切割出来的右中序、右后序作为参数），返回的值分别为左右子树根节点的值。今天还学了一下如何用tinyXml2库解析RSS文件，下载了slickedit。晚上学院组织了个签约指导会，好想知道我们专业到底是什么神仙找到了工作啊啊啊。听老师们用民以食为天这句话忽悠了这么多年，今天还是头一回将这句话和让我们把思路打开联系上，说什么我们各行各业都能去，比如有驾照就可以去试试物流开车去。。。真是要疯了。一下子又被影响到心态了，怒投了几家。还投了之前实习过的中粮，但其实不想去，工资低的可怜。。还是要继续努力转码才行，本专业找工作的事就顺其自然吧，也不抱太大希望。

1.222.完全二叉树的节点个数：可以把它当作普通二叉树去遍历，要遍历每个结点，代码更简单。此外还可以利用完全二叉树一直拆解成子树一定会出现满二叉树的特性（满二叉树的结点数量是2^n -1）去求结点数，可以少遍历内侧的一些结点，代码更复杂，效率更高，递归后序。2.110.平衡二叉树：递归后序遍历。出口条件：空结点。单层递归处理逻辑：分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。3.257. 二叉树的所有路径：递归前序遍历并回溯。当遍历到这条路径的最后一个叶子节点（注意没必要到空结点位置）就将这条路径放到结果集中去。递归处理逻辑：对左右子树进行遍历，并分别回溯（弹出路径的叶子结点，以及在递归函数控制权一级一级上交的过程中也弹出已经遍历过左右子树的相应结点，只保存公共路径，以岔到其他分支去）。4.404.左叶子之和：左叶子：首先是叶子结点，然后还要是它父节点的左子树。递归后序遍历。二叉树递归的题目思路都能理解，但是很容易忘记，只能后面多看多写几遍熟悉一下。今天学完了RAII资源管理、智能指针。加油！

1.226翻转二叉树：采用递归前/后序遍历的方式，递归出口（空结点）交换左右结点。2.101对称二叉树：采用递归后序遍历的方式，递归出口（左空右不空、左不空右空、左不等于右return false；左右都空return true），外侧结点（左的左，右的右）和内侧结点（左的右、右的左）进入递归比较。3.104二叉树的最大深度：递归后序遍历左右子树，出口是空结点，return 1+max(leftDepth,rightDepth)。4.111二叉树的最小深度：求根节点到叶子结点的距离！递归后序遍历左右子树，出口是空结点，左空又不空时返回1+rightDepth，左不空右空时返回1+leftDepth，都不空时返回1+min(leftDepth,rightDepth)。

1.二叉树前中后序遍历（深度优先搜索）：采用递归法思路更清晰，首先确定递归函数的返回值和参数（TreeNode* root, vector & vec）,然后确定递归的终止条件（当遍历到空指针的时候），最后确定递归结构体（直接把结果放入数组、遍历左节点、遍历右节点这三个执行的顺序决定了前中后）。2.二叉树的前中后序（迭代法）：迭代法的思路更复杂，前后序的解法类似，中序则不一样。3.二叉树的层序遍历：采用队列将二叉树每一层的结点入队，并记录队列的大小（一层的结点个数），当遍历到该节点时，首先将当前节点的值放入结果数组中，然后再将其左右节点入队。（所以在开始出队前，需要记录队列的大小，从而控制每次出队的元素是一层的结点个数）。

今天复习了一下前面两周学的算法题，思路大多还记得，就是很害怕代码实现时忽略一些细枝末节的东西！只能后面反复刷了！今天出去逛了一下，差点冲动消费充了1000，还好忍住了，我真棒！果然晚上回来就对那件衣服不感冒了！晚上还继续学了下函数模板，明天再接着把类模板、移动语义学完，基础部分就差不多了。后面再想想咋搞吧！转码真的好难，但是天坑找工作更难，已经快十二月了，悬着的心终于死了。只能继续努力转码了！看我室友天天发邮件找导师准备rp比我还焦虑，也不后悔完全放弃申博了，天坑博士也是天坑啊，读完又能去哪呢？发不了CNS这种正刊五年后还有正经学校要吗？真的很难说了。。不要再心存侥幸了，不给自己留这种退路才能全力以赴！我可以，其实很简单，其实并不难，学好了总有公司要的！明年最坏的情况就回家当全职女儿伺候我爸妈去，还有好几万奖学金没发，当零用钱也够花好几年的呢。不焦虑不焦虑，我可以，尽人事听天命！

1.150逆波兰表达式求值：利用栈求解。利用stoll函数将数字字符强转为long long类型压入栈里，当遇到加减乘除符号时（必须使用双引号来比较字符串），取出栈中的两个元素做相应的操作（后拿出来的元素要作为算式表达式中的前面的元素）。2.239滑动窗口最大值：利用deque双端队列来实现滑动窗口的增删元素操作。通过条件判断使得队列中最开始的元素一直是当前滑动窗口下最大的元素，元素入队时删除队列中小于该值的元素，保留比该元素更大的元素（循环比较que.back()）；滑动窗口出队时要考虑到在保证最开始元素为最大值的过程中可能已经将原本要弹出的元素弹出了，因此要通过判断滑动窗口要移除的元素value[i-k]是否等于当前队列中的最开始元素。3.347前 K 个高频元素：采用map来统计元素值以及出现的频率；采用优先级队列（小顶堆只维护k个数值，将数值更小的元素弹出，只留下k个更大的元素）。学完了多态。

1.232用栈实现队列：栈先进后出要实现先进先出的队列，就需要有两个栈stackIn和stackOut来实现出队列时元素的反转。当入队时，直接进栈，出队时，则首先考虑用于出栈的stackOut是否为空，如果为空的话，则循环将stackIn中的元素压入stackOut中，然后再从stackOut中弹栈。2.225用队列实现栈：一个队列即可完成，当要出栈的时候，就将队列中除最后一个元素以外的所有元素都出队列然后重新入队，再将第一个元素（原先的最后一个元素）出队。3.20有效的括号：利用栈先进后出的特性来对括号进行配对。循环遍历这组括号，遇到左括号时，分别将他们对应的右括号压入栈中，当1、栈为空，但字符串还未遍历完；2、遍历到的右括号与从栈中弹出的右括号对不上；3、遍历完字符串后，栈不为空，还有元素 这三种情况时说明无效。4.1047删除字符串中的所有相邻重复项：也是利用栈先进后出的特性来对相邻的重复字符进行一个删除操作。首先将字符串循环压入栈中，当遍历到的这个元素与栈顶元素相同时，就弹栈（删除）。还学习了多态、虚函数。

1.151翻转字符串里的单词：首先双指针法遍历字符串去除掉一些多余的空格，同时保证每个单词开始前给一个空格（在slow>0且s[fast] != ' '时，让s[slow]= ' '），然后resize当前字符串的长度，将其整个reverse，最后再将每个单词reverse。2.k55右旋转字符串：首先将整个字符串reverse，然后再分别将这两段字符子串reverse。3.28strStr()：KMP算法来匹配字符串，首先求出模式串的前缀表（next数组），求next数组的过程也要用到前面的记录，然后再循环遍历文本串，当遇到不相同元素时，根据next数组的值来回退模式串的指针（循环回退直到元素相同或者到0为止），继续比较直到完成匹配。4.459重复的子字符串：移动匹配的解法主要是先将两个字符串连接在一起然后掐头去尾，如果还能找到原字符串则证明存在重复的子字符串。用KMP算法可以降低时间复杂度。首先求出整个字符串的next数组，如果是由一个子串重复构成的话，next数组的最后一个元素值就是整个字符串的最大相同前后缀的长度。此时，最小子串的长度就等于整个字符串的长度减去next数组的最后一个元素值（len = s.size() - next[s.size()-1]）。通过len != s.size() && s.size() % len == 0可以推断出这就是最小的重复子串。

1.344反转字符串：双指针法，利用swap函数。2.541反转字符串II：这题要求比较多，先是指针移动到2k位置处，将前k个字符反转，若剩下的字符数少于k个则剩余的全部进行反转；若大于等于k个但小于2k，则反转剩余的前k个。这里要注意循环移动i时，不要固定的i++，而是直接让i一段一段的移动（i+=2*k）。3.k54替换数字：双指针法，首先计算出字符串里有多少个数字（s[i] >= '0' && s[i] 最近完成了单例对象自动释放、string的底层实现、关联式容器、词频统计、文本查询。还改完了师妹的综述，peter又在催文章了，尽量拖吧，拖到后面差不多要写毕业论文的时候一起写掉去。现在最重要的还是先学完C++的课和每天的算法题。

1.454四数相加：要和四数之和区分，这是分别从4个相等长度数组中各取一个，使其和等于0，得到这样的一个四元组。由于是4个独立的数组，因此不用考虑去重。首先定义unordered_map，key放a+b的值，value放a+b的和出现的次数。然后两层for循环得到a+b的值，和出现的次数；再用count来记录a+b+c+d=0的次数，两层for循环得到0-(c+d)的值，在map中找，如果找到了，则count加上该key对应的value值，而不是加1！2.383赎金信：与有效的字母异位词类似，定义一个record[26]数组，记录单词1各个字母的出现次数，然后再遍历单词2，将字母出现的次数--，如果发现有负数，则返回false。3.15三数之和：去重很麻烦，不要采用哈希法。采用双指针法，先排序，然后第一层for循环用来固定结果数组的第一个值，然后进行剪枝、去重操作（这步去重是nums[i] == nums[i-1]，说明nums[i]这个值已经用过了)，再定义两个指针分别位于i的后一个元素和最后一个元素，然后进行判断，不断收缩这两个指针。4.18四数之和：在三数之和的基础上再在外部套一层for循环，注意两层剪枝、两次去重，注意边界条件，以及target为负数的情况。