春季四个月刷题

因为这半年要实习，平时没太有时间自己学习，决定每天抽出一些时间做题，希望能坚持下去，这样到暑假和秋招找全职就会更从容一些。

计划：周一至周五每天三个题目，周六周日每天五个题目，这样每周25题，一个月100题，四个月400题。

补充内容 (2020-2-12 12:18):
现在做到100题了，上周末做了contest、感觉以后可以一直参与下去，一开始尽量每次都能作出两三题吧，感觉前面的两三题也不是特别难

1.17 做题

102. Binary Tree Level Order Traversal. BFS使用Queue进行层级遍历；注意每次遍历的时候都要预先记录Q的size，然后把Q中的所有node都poll出来然后先左后右offer进去；每次循环处理的都是盖层的节点

100. Same Tree. 这里用的简单的recursion来做；首先比较base case，也就是两个tree的root的情况，如果都为空就是true，只有一个为空就是false，都不为空但是value不同也是false；比较完root以后，就要进行recursion比较，也就是要对两个tree的左子树和右子树进行分别比较；因此分别以左右子节点为root，recursion调用验证即可

101. Symmetric Tree. 这个题目是考察一棵树是否对称，和前一题目类似；考察对称其实就是考察其左子树和右子树是否对称，因此需要有一个helper function；对于左右子数来说，首先它们的root节点应该是相同的，然后进行recursion对比，左边的左等于右边的右，左边的右等于右边的左

1.21 做题

206. Reverse Linked List. 这个题目是反转链表，反转链表有recursion和iteration两种方法；iteration的方法就是一组一组进行反转，首先获取当前node的next，然后使得当前node的next指向它的prev，然后让它的prev指向当前node，而当前node则指向next，这样一轮即可完成反转；recursion就比较简单，先调用recurison解决head.next，这样只剩下head的next没有反转，让head的next的next指向head，并且让head的next指向空即可

141. Linked List Cycle. 这个题目的方法就是快慢指针；具体来说，判断一个list有没有环存在，就设置slow和fast两个指针，slow每次往后走一步，fast每次往后走两步；如果fast最后走到了null，说明这是线性的，不存在环；如果最后fast和slow相遇了，就说明肯定存在环，这是因为fast比slow快，如果存在环的话，肯定fast会追上slow的

24. Swap Nodes in Pairs. 这个题目我用的recursion做；recursion先解决除了前两个以外的后面的，然后获得一个subHead；那么接下来，就先保存head的next，然后head的next指向subHead，最后next的next指向head，这样返回head就可以了，recursion非常简单；iteration的话可能就麻烦一点，每次循环swap一组，然后prev、cur、next往后移动

3.19 做题

388. Longest Absolute File Path. 这个题目的思路是这样，首先要把文件/文件夹的名字从给定字符串中提取出来，这时就需要使用“\n”来分割给定字符串、生成一个String Array；然后发现即使这么做以后，Array中的每一个String仍然有“\t”，那么这个“\t”就代表了当前文件/文件夹的级别，没有\t就说明是dir，有几个\t就说明这处在第几层；那么这里实际上是需要进行定位，对于每一个文件/文件夹都要定位它的父文件夹、父父文件夹这样，那这当然不是在这个Array中单纯往前找就可以找到的，因此这里使用了一个Stack作为辅助；Stack存储的，就是当前这个文件/文件夹所存在的目录路径的从一开始的整体长度，而stack的每一个元素都是一个文件/文件夹的绝对路径长度；维护stack的方法就是（stack有一个0元素作为最下面的元素），每一次遍历到一个array中的string后，先检查它拥有的tab个数，然后算出它的层级，如果这个string的层级比stack的size要小，那就说明现在这个string代表的文件/文件夹相对于stack存储的最上面的那个数字代表的文件/文件夹后退了，那么stack就应该持续地poll，也就是相当于后退的操作，知道stack的size和当前string的层级相同，这就意味着stack顶的数字代表的文件夹，就是当前string代表的文件/文件夹的父文件夹；那么这时只需要获取到当前string的长度，加上stack顶的长度，再减去当前string的tab数量，再加1（表示中间的/分隔符），就表示当前string代表的文件/文件夹的绝对路径长度了；那么如果当前string拥有"."的话，就说明这是个文件，那就可以和全局最大进行比较更新了

394. Decode String. 这是一个String的解码题，给定一个编码好的String，编码的方式就是这样k[encoded_string]，也就是比如可能给定的String是这样“3 [ 2 a b [ a b 3 [ a b c 4 [ a b ] ] 2 [ a ] a b c d ] 5 [ a b ] e f ] g h”，意思就是说，k代表后面的括号内圈定的字符串的重复次数，很容易理解；那么具体在做的时候，肯定是需要从左到右遍历给定字符串的每一个字符的，那么就会遇到四种情况，也就是数字、左括号、字符、右括号；当遇到数字时，就进行统计这个数字到底数值为多少即可，比如现在是325[ab]的话，扫描到了3，那么统计方式就应该是k = k * 10 + c - ‘0’；如果遇到的是字母的话，那当然就应该有一个StringBuilder去append这一串字母；问题在于左括号和右括号分别代表什么；左括号就代表，当前统计完毕了一个数字，而这个数字之前可能还会有已经构建完毕的StringBuilder，因为括号可能是一层套一层，从左到右并不一定是左右括号交替出现的，就比如这种情况“3 [ a b c 4 [ a b ] ] ”，从左到右的话，先是构建abc，然后计数了4，然后紧接着又出现了一个左括号；而左括号的后面，就需要开始构建新的StringBuilder，当染也有可能需要重新开始计数，这就比如这种情况“2 a b [ a b 3 [ a b c 4 [ a b ] ] 2 [ a ] a b c d ]”，第一个左括号后面首先要构建ab，然后计数3；那么遇到左括号的话，既然前后都可能会有构建StringBuilder的需求和计数的需求，那就应该把左括号之前构建好的StringBuilder和计数完毕的数字，各自放到一个Stack当中先保存下来，然后把全局的StringBuilder和全局的计数归零，用来构建左括号后面的需求；而如果遇到右括号的时候，简单来看就意味着一个StringBuilder构建完毕了，但同样也意味着，这组括号结束了而它前面的k应该生效了，也就是说decode string的过程中，现在应该根据k去重复构建这个String了；那么就比如对于这种情况来说“2 a b [ a b 3 [ a b c 4 [ a b ] ] 2 [ a ] a b c d ]”，当遇到的是4 [ a b ]的这个右括号，现在全局计数是0，而全局StringBuilder则是ab，而这组括号的左括号之前的4和abc都已经被放到各自的stack当中了，因此就应该从stack中把4和abc拿出来，首先根据4重复ab，然后再把重复获取到的string给append到abc的后面；也就是说遇到右括号，就说明现在应该完成一组构建了，也就是decode的过程；在这个题目中，需要维护的是一个全局的计数和全局的StringBuilder，全局计数其实无所谓，因此计数完毕以后，往后走肯定是直接左括号（否则就失去了计数的意义），因此计数完毕后肯定就直接加到stack当中了；但是对于全局StringBuilder来说，当构建完毕一个以后，它后面可能遇到的是数字，也可能遇到的是右括号；如果遇到数字的话，意味着马上要遇到左括号，那么也会驾到stack中；而如果遇到的是右括号，就意味着这个StringBuilder需要重复然后加到从stack中取出的StringBuilder后面，这时，当加完以后，这个全局的StringBuilder应该保存的就是这个加完的结果，那么这时再往后的话，对于一个右括号来说，后面可能是数字、可能是字母、也可能仍然是右括号；如果是数字的话，这个全局的StringBuilder也就不要动了，直接等着数字后面的左括号、然后一起加到stack中即可；如果是字母，那这组字母肯定不需要重复，那直接加到这个全局SB后面就可以；如果仍然是右括号的话，就说明有一组括号结束了，那么这个全局的StringBuilder就又要重复k次，然后加到stack中当前的最顶的StringBuilder后面；也就是说这个题目，遇到左括号加到stack中，遇到右括号从stack中拿出，就像是recursion的往下走和往上返的过程，因为括号都是完美对称的，所以一个全局的StringBuilder，按照上面的方式，肯定会最终存储所有decode后的String的

224. Basic Calculator. 这个题目和之前的decode string一样，要理解遍历给定String过程中，遇到什么样的字符需要做什么样的事情，同时要搞清楚全局维护的都应该是哪些变量；这里全局维护了一个sign、一个res、一个num、以及一个stack，res是全局结果，num是每一次统计到的数字、sign是当前应该计算的是+还是-；如果遇到数字，那么就更新num；如果遇到+或-的运算符号，那么就说明前面的数字扫描完了，扫描完了就要加到结果当中去，而当前的sign（注意不是现在扫描到的符号）正好就一定是扫描完的数字的前面的符号，因此用这个sign乘扫描完的数字，就可以加到结果中去了，然后再根据现在扫描到的符号更新sign，同时num归零；如果遇到括号的话就应该注意；如果是左括号，那么左括号前面一定是符号，也就是说现在的num已经归零，而sign存储着这个符号，res则存储着现在已经获取到的结果；而左括号后面一定是一个独立的表达式，也就是先是数字然后又是符号，那么sign现在存储的符号肯定不能直接作用于这个左括号后面的数字，而是作用于这组括号整体的，res也是，不能直接用sign和这个数字相乘；因此出现左括号就意味着要另起炉灶，重新开始计数num、获取sign、加和res了，那么现在已经有的sign和res就要放到stack当中进行存储，先放res再放sign，然后进行重制；那么左括号后面的数字和符号处理方式和之前的一样，接下来就会遇到右括号；遇到右括号就意味着这一组括号内部的表达式扫描完毕了，而右括号前面的一定是数字，因此这个num就应该乘它前面的sign然后加到res当中去，这样这组括号内部的表达式的值就处理完毕了，然后要做的就是把这个值也就是当前的res和这组括号之前的加起来，也就是说，要重新获取到这组括号之前的符号和res，也就是已经存储到stack当中的，因此先poll出来之前的sign，再poll出来之前的res，用prev_sign乘当前的res，再加到prev_res上即可；那么最后结束循环时，可能还是会遇到一个扫描的数字，因此在最后获取到num，再乘sign加到res即可，最后返回res

227. Basic Calculator II. 这个题目是给定一个表示四则运算的表达式String，没有括号；注意的就是calculator的符号滞后性，即每当扫描到一个符号的时候，当前的sign变量总是存储着前一个符号、而num变量总是存储着当前扫描到符号的前一个数字，滞后性就是说，每当扫描到一个符号，应该运算的总是前一个符号和前一个数字，运算完毕后，再把num归零、用sign记录当前符号；另外calculator的stack，这里应该存储的就是每次运算完毕的数字，也就是每次遇到符号时进行计算前一个数字和符号的结果需要offer到stack当中；具体来说，每当扫描到数字时，那就加到num里面去；每当扫描到符号时，就说明前面扫描的num已经构建完毕，同时当前的sign变量存储的是构建完毕的num之前的那个符号，那么如果是+或-的话，直接把当前构建的num乘1或-1，添加到stack中；而如果是*或/的话，考虑到运算优先级，这里就不仅仅需要当前的num和当前的sign了，还需要这个sign更前面的那个数字，也就是之前被offer到stack中的那个prev_num，因此就要把这个prev_num给poll出来，和当前的num进行*或/运算，获取到结果之后再offer进stack中；注意如果当前扫描到最后一个的时候，最后一个一定是num，而且前面还有一个符号sign，因此如果扫描的是最后一位，就需要和遇到符号的情况一起处理；因此如果遇到符号或者扫描到最后一位，就需要进行总结计算，把num和sign的结果放到stack当中；扫描完毕后，从stack中一个一个取出结果，相加即可，因为在之前遇到符号的时候，总是乘1或-1，或者如果有*或/的情况就会已经运算完毕，因此最后简单相加即可

385. Mini Parser. 这个题目本质上讲还是扫描String然后对不同情况下的字符进行分类讨论，而如果遇到括号一类的特殊字符，就需要往下走或向上返，并用一个stack来进行模拟；需要维护一个stack来存储往下走时上一层的NestedInteger，维护一个cur来保存当前层的NestedInteger，每当一层扫描完毕之后，当前的cur就应该加入到上一层的NestedInteger、也就是需要从stack中poll出来，并且返回上一层、也就是需要更新cur回上一层，因此这个题目和decode string以及basic calculator带括号的很相似；当遇到左括号的时候，说明要往下走一层，因此表示当前层的cur就需要被添加到stack当中去，然后cur归零准备下一层；当遇到右括号的时候，说明当前层的一个integer扫描完毕，需要被添加到当前层的cur当中，当谈也意味着这整个一层都扫描完毕了，要回归上一层，因此就从stack中poll出上一层的NestedInteger，然后把这一层的cur整体添加到上一层的NestedInteger当中，然后由于往上返了回到了上一层，cur记录的也就应该是变成上一层的了；当遇到逗号的时候，前面要么是右括号要么是数字，右括号的情况刚刚已经讨论过了，如果是数字的话，就简单给当前层的cur添加一个数字即可；这里注意如何扫描数字，使用的不再是num = num * 10 + c - '0'了，而是限定了一个left，left只是指向特殊符号的后面，然后和遍历的right进行圈定字符串而已，是另一种方式

1.11 做题

27. Remove Element. 题目要求移除给定array中的目标元素，inplace，然后返回一个长度，使得从0开始到这个长度为止的原array的subarray都不包括这个目标元素；方法是双指针，快指针每次都往前走；如果快指针遇到目标元素，就继续往前走；如果快指针遇到的不是目标元素，那么把这个元素复制给慢指针，然后快慢指针一起往前走；最后返回慢指针的index，实际上也就是慢指针前面的subarray的长度

26. Remove Duplicates from Sorted Array. 这题目要求移除给定array中重复的元素，返回一个长度，使得这个长度前面的subarray不包含重复元素；使用双指针，注意快慢指针起始位置都是1，因为不管怎样最初始位置的元素都是一定要保留的；快指针一直往前走，如果遇到当前元素和此前元素相同的情况，快指针就一直走，直到不同或者快指针到达array末尾；如果到达array末尾就返回慢指针index，否则说明快指针遇到了不同元素，不同元素需要保留，因此复制该元素到慢指针位置，然后快慢指针同时往前走；慢指针的左侧是所有的不包含重复元素的subarray，不包含慢指针本身

80. Remove Duplicates from Sorted Array II. 这个题目和上一题的区别就是，给定一个数组让最多保留两个相同的元素；同样是快慢指针，上一题的解法是j和i-1比较，如果是不同的元素就把j复制到i的位置上；这个题目就应该是把j和i-2比较，如果是不同的元素就把j复制到i的位置上；这是因为对于这个sorted的数组，只需要j和当前已经保留的这些元素不同即可；那么对于全部不相同的情况来说，j必须和当前已经保留的最后的那个元素进行比较，因为i-1和i之间只有两个元素，必须都不能相同；而这个让保留两个相同元素的情况，j只需要和当前已经保留的倒数第二个元素进行比较即可，因为允许保留两个元素，对于i-2和i之间的三个元素，i-2和i-1可以相同也可以不同，但是无所谓，只需要i和i-2不同即可满足要求了

277. Find the Celebrity. 这个题目要求找出从0到n-1这n个人中，被所有其他人“认识”但是不“认识”所有其他人；思路就是首先把所有人过滤一遍，暂时指定一个candidate，看看这个candidate认不认识其他被过滤的人，如果认识的话，这个candidate就作废，换成当前这个被遍历到的被他认识的人；第一轮过后，至少可以确定其他所有人，除了这个candidate之外都违反了规则了，这是因为第一轮的时候被个人都被遍历，检查是不是被candidate认识，如果不被candidate认识的话就会继续遍历，如果被candidate认识的话那么candidate就会换成这个人，然后对这个人继续进行检查；但是现在仍然不能确定这个candidate是不是违反了规则，所以针对这个candidate仍然要进行第二轮过滤，看看对于这个人来说，其他所有人是不是认识他并且他是不是不认识其他所有人

189. Rotate Array. 这个题目基本思路就是，先reverse前半部分，再reverse后半部分，最后reverse全部

1.12 做题

41. First Missing Positive. 题目的大体思路就是，数组对应位置上需要尽量保证出现正确的正数，在将所有元素尽量归位后，再从头遍历数组检查哪一个位置上没有出现正确的正数，检查出来的就是结果；即对于长度为n的数组来说，index 0上应该出现的元素是1，index 6上应该出现的元素是7，index n-1上应该出现的元素是n；所以首先需要对整个数组遍历，对于每一个元素来说，如果它是正数、如果它不是特别大的数（数值不大于数组长度），那么就应该在数组中有一个适合它的位置，也就是比如在一个长度为9的数组中，扫描了6，那么6就应该出现在index为5的地方；那么对这个元素所应当出现的位置进行检查（比如现在在index为3的地方扫描到了6，那么6应该出现在index为5的位置，因此就去index为5的位置检查），如果发现这个位置上并没有当前元素（也就是说index为5的位置却出现了8），那么就把当前index为3的位置上的6和index为5的位置上的8进行互换，从而保证“数组对应位置上出现了正确的正数”；而当前index为3的位置的数字则是8了，那么继续对8应该出现的位置，也就是index为7的位置进行检查；这样检查下去，直到被换过来的数字是：1）正确的正数、2）不是正数、3）特别大的数，那么就继续往后扫描；而当前的这个位置上没有出现正确的正数，就可能会成为要返回的结果；总之这样扫描下来，可以保证在数组中的每一个“合适”（大于0又不大于数组长度）的正数，都出现在它们应该出现的位置；而对于其他的那些位置，并没有放置应该出现的正数；因此第二遍从前往后扫描的时候，最先发现的没有出现正确正数的位置，所应该出现的正确的正数，就是First Missing Positive

299. Bulls and Cows. 这个题目的解法是，遍历secret和guess字符串，用one pass分别计算bulls和cows；对于bulls来说，只需要当前遍历位置的两个字符串的元素相同即可；当不为bulls的时候，就需要把当前遍历位置的两个不同的字符串元素，分别添加到这两个字符串所对应的HashMap当中；HashMap的key就是字符，value则是字符在对应字符串中的出现次数；那么对于secret当前位置的字符来说，首先要去guess对应的HashMap中检查是否曾经出现，并且检查出现次数：如果曾经出现切次数大于0，说明guess中尚有字符可以进行匹配，因此cows增加，同时因为secret和guess的这个字符进行了匹配，因此两个字符串对应的HashMap的对应键值对都应该更新，也就是出现次数减1；而对于guess的当前位置的字符来说，也是应该做同样的操作

134. Gas Station. 这个题目的想法就是，如果A站不能到达B站、且B站之前的站A站都能到达，那么A站到B站间的所有站都不能到达B站（这很容易理解，因为如果A站能到达之前的所有站，而之前的某一站又能到达B站，那么A站肯定能到达B站）；而判断当前A站能不能到达B站的标准就是，从A站开始剩下的油，一路开过去加油耗油，到B站的时候是不是仍然存油量大于0；因此遍历gas和cost两个数组，对于每一个位置都进行gas - cost的操作，并把结果加到remain变量当中；如果加完之后remain大于等于0，就说明从开始记录remain的那一站到当前的这一站，油量是足够的；否则，说明开始记录remain的那一站根本无法到达当前的这一站，因此start只能从这一站开始记录；同时要维护一个debt变量，这个变量的意思就是，如果出现remain小于0的情况，那么先把油欠着，把负数加到debt中，因为这是一个circle，当车从start开到最后一站的时候，可能仍然剩下很多remain，足以弥补这些debt；所以最后看看remain和debt的和是否大于等于0，来判断有没有结果

118. Pascal's Triangle. 这个题目暂且用了非常简单直观的方法，就是从{1}开始加到res中，然后每一次加到res中的ArrayList，都是基于当前res中最后一个ArrayList里面的数值的；也就是先拿出来最后一个ArrayList，然后对于这个里面的每相邻的两个数，都进行相加，然后加到最新的一个ArrayList中，加完以后加到res即可

119. Pascal's Triangle II. 这个题目就是前一题稍微的变种，只要有了上一层的list，那么这一层的list就inplace进行更改即可

1.13 做题

28. Implement strStr(). 这个题目应该使用KMP，更直观的方法就是，对于haystack来说，对于它的每一个位置，往后找和needle长度相等的substring，然后把这个substring和needle进行比较，如果相同就返回substring在haystack中的index

14. Longest Common Prefix. 这个题目就把整个String数组排列一下，然后取第一个和最后一个，找它们的公共prefix即可；因为排序一壶所有String都是按照字母排列的，，所以prefix很容易找

58. Length of Last Word. 这个题目直接用string的内置方法split，按照空格将string划分为string数组，然后直接定位到最后一个位置的String，获取长度即可

1.14 做题

387. First Unique Character in a String. 这个题目一开始我做的非常麻烦，先建立了一个linkedHashMap，然后把所有String中的char都put进去然后计数；接下来在从前往后遍历这个LinkedHashMap，发现第一个count为1的字符就break掉并记录这个字符；最后拿这个字符去原String一个一个比较，第一个匹配的就返回这个的index；然后我一般想到的方法就是two pass的，也就是用一个HashMap，先计数，然后再直接遍历String一个一个去看是否在map中的计数是1，如果是的话就返回这个index；当然one pass的方法就是，在maintain一个LinkedHashMap的同时maintain一个Set，遍历这个String然后如果当前char没有出现在set中的话，就同时添加进set和linkedhashmap中，当然在map里value是它的index；如果出现在set中的话，去检查map里面有没有，如果有的话remove掉，因为这是重复出现的；linkedhashMap这里就装着所有不重复的字符，并且按照出现的顺序进行排列

383. Ransom Note. 这个题目的是要判断，能不能把B字符串的所有字母拆开，然后用这些字母拼接成A字符串的；那么方法就是，把B字符串用Map进行字符计数，然后遍历A字符串；对于A的每一个字符都去B中查看，看是否存在并且计数大于0；如果不是这样就说明不能拼接，否则更新Map中对应字符的计数减1

344. Reverse String. 逆转字符串，这里给定的是一个charArray形式的字符串，那么直接左右指针swap，然后left++ right--即可

1.15 做题

151. Reverse Words in a String. 这个题目有很多String相关的方法可以直接使用，比如String.trim()就是去除String前后的空格的，String.split("")就是根据参数来将String分割成String数组的，String.join就是把一个String数组重新拼接成字符串的

345. Reverse Vowels of a String. 题目要求把给定字符串中的所有元音字母进行reverse；思路就是使用双指针左右遍历，当左右指针都指向元音字母时才进行swap；在双指针遍历之前，提前把元音字母都在Set中准备好，以便双指针遍历时进行元音字母检查

205. Isomorphic Strings. 这个题目就是查看两个字符串的形式是否匹配；实际上就是看两个字符串的字母之间是否相互建立了一一对应的关系；因此思路就是，对于其中的一个String，建立Map，然后把当前字符和另一个String对应位置的字符加入进去；在之后的检查中，如果发现已经出现的字符在另一个String中出现了其他的对应字符，就可以判错；当然仅仅如此还不行，对于另一个String来说反过来也需要这种操作，才能保证“一一对应”

1.16 做题

144. Binary Tree Preorder Traversal. Binary Tree的preorder遍历；这里当然使用的是iteration的方法，也就是用一个Stack进行存储节点辅助；方法就是，对于当前的root，首先offer到stack当中，然后进行循环；对于每一个从stack中poll出来的节点，都先取右节点放入stack、再取左节点放入stack；由于这是一个stack，放在最下面的右节点在从stack中poll的时候，总比左节点poll的晚；而循环下来，左节点总是先poll出来然后加到res当中；这样也就保证了preorder的打印，即首先从stack中poll出来当前节点，然后先右后左获取子节点并加入到stack中，最后当前节点加到res里面；其实preorder的iteration方法和level-order的遍历非常类似

94. Binary Tree Inorder Traversal. 这道题目仍然使用iteration的方法，使用Stack作为辅助存储；这个题目稍微复杂一些，需要一个helper node，这个helper node是需要指向在inorder遍历过程中的“下一个”需要进行遍历的节点，也就是left - root - right这样的顺序；一开始helper node需要指向root；然后开始循环后，首先将helper指向的节点offer进stack当中，然后helper就指向下一个进行遍历的节点；由于这是inorder，所以helper一开始总是需要指向left，而沿途经过的节点就都依次放到stack中；当helper为空的时候，也就意味着上一个被offer到stack中的node就是这个子数的最左子节点了，因为helper作为它的left是空，因此从stack中取出最顶的node并记录它的value到res里面；然后helper再指向该点的右子节点，然后再重复以上所有过程；也就是总得来说，一头扎到底，沿途记录节点，如果为空就poll出栈顶节点，然后helper拐弯指向right节点再一头扎到底

145. Binary Tree Postorder Traversal. 这个题目仍然使用iteration方法，使用Stack；题目是post-order，也就是对于一个节点来说，必须得其左右子节点都打印完毕后才能对其进行打印；因此对于一个当前节点就可能有三次遍历，即从上面走过来的第一次遍历、从左子节点走回去的第二次遍历、从右子节点走回去的第三次遍历；这三次遍历可能不一定全部发生，因为不一定每个节点都有左右节点，但是总可以通过记录“前一次”遍历节点的方式，判断这次遍历是从哪个方向过来的，从而判断这是第几次遍历；通过获取Stack顶部的节点（peek）来获得当前节点；对于当前节点是前一次节点的子节点的情况，说明这是第一次遍历，因此就应该将当前节点的左右子节点分别检查是否为空，不为空就offer进stack中，否则打印当前节点并从stack中poll出去；对于前一次节点是当前节点的左子节点的情况，说明这是第二次遍历，因此就应该将当前节点的右子节点检查是否为空，非空就offer，否则打印当前节点并从stack中poll出去；对于前一次节点是当前节点的右子节点的情况，直接打印并poll即可；每次循环都要更新前一次节点，另前一次节点指向当前节点

1.18 做题

226. Invert Binary Tree. 这个题目让反转一棵树，使用recursion的方法；首先判断base case，检查root是否为null；然后对left和right子节点调用recursion方法，获取已经反转好的左右子树；最后对于当前root节点来说，进行左右invert，也就是把左子树派给右节点，右子树派给左节点，最后返回root即可

257. Binary Tree Paths. 略麻烦，要收集好所有从root节点到叶子节点的垂直路径，然后收集到res当中；所以首先需要有一个List存储各个路径，然后需要有一个String去记录路径；因此写一个dfs的helper function，参数是String和List，当然还有TreeNode；对于当前root来说，首先判断是否左右子节点为null，如果是null的话就是叶节点，那么直接把root给的value给加上String里面，然后add到list当中；如果左右子节点不为null，比如left不为null，那么至少可以往左继续走，因此就把root的value加到String里面，然后再加一个“->”表示后面还有节点，接下来调用recursion function即可；对于right的情况也是如此

112. Path Sum. 题目要求验证是否这个tree从root到leaf的整个路径的和是等于给定的sum的，考虑使用recursion方法；首先判断root是否为null，如果为null一定是false；然后判断root是否有左右子节点，如果root本身就是叶节点，那么直接判断root的value和sum是否相同；如果root还拥有左右子节点，那么对其左右子节点分别进行recursion判断，同时把sum减去当前root的value，从而能够往后验证

113. Path Sum II. 这个题目和前面的几乎是一样的；区别在于这里需要记录所有valid的path才行；仍然用recursion，需要维护一个总的res，和记录每个path的list，每一个recursion开始的时候，都需要将当前root的value添加到path中；在recursion当中，如果当前节点是叶节点并且其value和sum相同，那么就把当前这个path复制到res当中去；如果当前节点的某个子节点不为空，那么就顺着这个子节点往下进行recursion，把path和res都传入，当然sum要减去value；最重要的就是，在recursion后，path需要remove掉最后的那个元素，也就是remove掉刚刚添加进去的这个子节点的value，这是因为每个节点有两个子节点，recursion完左边后，path就会有左节点，那么同一个path再去recursion右边的话，左节点就一定需要remove掉

78. Subsets. 这个题目是典型的dfs例题，给定数组作为一个大集合，希望找到大集合的所有子集；这里对于每一个元素来说都有两种情况，要么添加进去要么不添加，recursion到底的base case就是当前遍历的元素到了给定数组的头了；recursion tree每个节点分两叉，要么添加进subset要么不添加；recursion tree的深度就是给定数组的长度

1.19 做题

90. Subsets II. 这个题目和上一题有些类似，题目中要求多了可能在给定数组中出现重复元素的，但是不能允许结果中包含重复的subset；也就是说同一个元素可能前后出现两次，如果有一个subset是加了前面的没加后面的，另一个subset是没加前面的加了后面的，那么这两个就算是重复的subset，但是在同一个subset内，仍然是可以允许出现重复元素的；这个题目的第一个解决办法就是和上面的完全一样，只不过在一开始的时候要把给定数组进行排序，然后用一个Set去装载整个结果，最后输出的时候就吧Set转化会List，通过Set就可以保证没有重复的subset；第二个解决办法就是，使用另一种recursion的思路，也就是在recursion function内部用一个for循环，从当前index循环到给定数组的最后，那么对于循环中的、除了当前index对应的元素外的、每一个数组元素，都要考察是否和前一个数组元素相同，如果相同就略过，然后考察完毕后，再把当前元素添加进subset中，然后调用dfs并且设置index为当前扫描的位置+1，最后在删除这个元素，而这里的recursion base case就是只要当前index<=数组长度，就进行添加，并且添加完毕后不return；这里就涉及到两种recursion的思路，一种是对于每一个元素都考虑是否进行添加，每一层有两叉，一共层数是元素的个数；另一种是在每一层都从当前元素开始往后走检查是否需要添加一直到最后，每一层实际上有元素个数个叉，一共层数也是元素个数；这里不懂的地方就是对于两种方法为什么都需要实现进行数组的排序，此外对于第二种方法为什么要进行除了当前recrusion的index外的重复检查也不懂

77. Combinations. 这个题目仍然是典型dfs，和subset很类似；第一种思路就是对于同一个数字考虑是不是要添加进combination当中，然后从1一直到n这样，因此是2叉树，一共n层；这里要注意base case和dfs的signature，signature的设计就是，除了n和k还要有一个当前数字，base case则是首先看k是否已经为0，也就是看comb中是否已经有了足够的数字，然后再看cur是否大于n，如果都讨论完的话就直接return，recursion的时候，对于添加的情况需要k - 1，否则不变k；另一种思路就是recursion内部进行for循环，base case只考虑k为0的情况，for循环内部就是简单的从当前数字开始循环到n，然后往comb中添加当前的i，然后调用dfs同时k - 1，最后再从comb中remove出去

39. Combination Sum. 这个题目和combination有类似，给定一个数组，里面的元素都可以用任意次，使得它们之和等于target；解法就是，recursion function内部是for循环，从当前index开始往后遍历，遍历到的元素添加进comb当中，并且调用recursion的时候，需要对target进行减去遍历到的元素，同时recursion的index就是当前的i而不加1，因为考虑重用

40. Combination Sum II. 这个题目和上一题目的区别就在于，这里给定数组的元素不可重用，但是给定数组内部可能会出现重复的元素；这个题目和上一题目的区别，就和subet II和subset I的区别完全一样；需要更改的地方就是，首先在recurison内部的for循环当中，对于大于当前index并且当前元素和前一个元素相同的情况直接略过，然后在recursion call的时候，因为同一个元素不可重用，因此index需要是当前的i + 1才行

216. Combination Sum III. 这个题目和前面两道题大致一样，只不过这里给的不是数组，而是规定了从1到9这9个数字当中挑k个，组成和为n的组合；所以就相当于是给定了一个长度为9、元素是从1到9的数组，并且规定了comb的数量只能为k；因此在recursion function当中，每当n减到0并且此时的comb数量是k的话，就添加到res当中，否则如果comb超过k了就return；在内部的for循环中，从当前的数字一直循环到9，里面的recursion调用就单纯用n减去当前的i并且当前数字加1即可