法律顾问每周工作总结 小编:艳芬 245阅读 2020.03.31 一、工作内容：
1、应要求，就客户已经、面临或者可能发生的纠纷，进行法律论证，提出解决方案，出具交涉函件，发表法律意见，或者参与非诉讼谈判、协调、调解；
2、应客户要求，讲授法律实务知识；
3、应客户要求监测与客户相关的法律法规的发布和修改；
4、为其他部门提供法律支持。
二、下周工作安排：
1、解答法律咨询、依法提供建议或者出具法律意见书；
2、协助草拟、制订、审查或者修改合同、章程等法律文书；
3、应客户要求，参与磋商、谈判，进行法律分析、论证；
4、受客户委托，签署、送达或者接受法律文件。

　　
前几天发了字节面试算法100题，这一篇给牛友们整理了答案，楼主整理过程中又对题目做了归类，所以和之前的题目顺序不完全一致，这一篇包含了100题中动态规划和贪心，数组，排序，栈+队列+链表，二叉树相关的算法题题解。一些不易分类的算法题，场景题和智力题答案下一篇发出来。

　　整理不易，感觉有用的话点个赞呀，亲！????（牛客网的编辑器插入代码必须一个一个来，楼主从自己的笔记中一点一点复制过来，眼睛要瞎了??????）

　　很多题目的题解参照了牛客和力扣中的优秀题解，一些题目中也贴出了题解链接。楼主能力一般，水平有限，难免有错误和遗漏，有问题的地方欢迎牛友们在评论区指正，有更好的解法也可在评论区分享，万分感谢。

　　【算法题】

　　动态规划和贪心

　　算法题：买卖股票的最佳时机（只能有一次买卖，可以最多两次买卖，不限次数）

　　
股票问题通用解法详解参考：

　　
最复杂的情况是限制交易k次，状态转移方程无法化简，其他情况均可化简为二维或一维动态规划。

　　
复制代码

　　 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465//一次买卖public?class?Solution?{????public?int?buy(int[]?price)?{????????int?n?=?price.length;????????int?ans?=?0;????????int[][]?dp?=?new?int[n][2];????????dp[0][0]?=?0;????????dp[0][1]?=?Integer.MIN_VALUE;????????for(int?i?=?1;i?

　　优化：只与相邻的一个状态有关，那么可以只记录前一个状态，不使用数组，空间降到O

　　(1)public?class?Solution?{????public?int?buy(int[]?price)?{????????int?n?=?price.length;????????int?ans?=?0;????????int?dp_i_0?=?0;????????int?dp_i_1?=?Integer.MIN_VALUE;????????for(int?i?=?1;i?=?1;?k--)?{????????if?(i?-?1?==?-1)?{?????????????/*?处理?base?case?*/????????????dp[i][k][0]?=?0;????????????dp[i][k][1]?=?-prices[i];????????????continue;????????}????????dp[i][k][0]?=?max(dp[i-1][k][0],?dp[i-1][k][1]?+?prices[i]);????????dp[i][k][1]?=?max(dp[i-1][k][1],?dp[i-1][k-1][0]?-?prices[i]);????}}//?穷举了?n?×?max_k?×?2?个状态，正确。return?dp[n?-?1][max_k][0];

　　 剑指原题，剪绳子。

　　 1.动态规划：每次剪一刀之后，剩余部分还可以继续剪，那么就是计算出所有可能的情况，取最大值。自底向上改善递归从上而下重复计算的问题。

　　 时间复杂度O(N^2),空间复杂度O（N）

　　=4的情况，跟n

　　 2.贪心算法：可以证明，每段长度为3是最大乘积。

　　 时间复杂度O(logN),因为乘方运算的时间复杂度是logN。当

　　 数据特别大时，只能使用贪心算法，因为动态规划枚举每个状态需要大量的空间。

　　 复制代码1234567891011121314151617public?class?Solution?{????public?int?cutRope(int?target)?{????????if(target==2){????????????return?1;????????}else?if(target==3){????????????return?2;????????}????//pow(n,m)是求n的m次方????????if(target%3==0){????????????return?(int)Math.pow(3,target/3);????????}else?if(target%3==1){????????????return?4*(int)Math.pow(3,target/3-1);????????}else?{????????????return?2*(int)Math.pow(3,target/3);????????}????}}

　　 算法：接雨水（leetcode 42）

　　 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

　　 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

　　 示例:

　　 输入: [0,1,0,2,1,0,1,3,2,1,2,1]

　　 输出: 6

　　
思路：

　　
对于每一列来说，他能存的雨水量是他左边最高墙和右边最高墙中较低的那堵墙的高度减去自身墙的高度。所以可以用数组记录每列左右最高墙的高度，然后计算每一列可以存的雨水量。

　　
动态规划：时间复杂度O(N)，空间复杂度O(N)。

　　 复制代码1234567891011121314151617181920212223class?Solution?{????public?int?trap(int[]?height)?{????????int?len?=?height.length;????????if(len?==?0??len?==?1)?return?0;????????int[]?left?=?new?int[len];????????int[]?right?=?new?int[len];????????left[0]?=?height[0];????????right[len?-?2]?=?height[len?-?1];????????for(int?i?=?1;i?=?0;i--){????????????right[i]?=?Math.max(height[i?+?1],right[i?+?1]);????????}????????int?sum?=?0;????????for(int?i?=?1;?i??height[i])????????????????sum?=?sum?+?(min?-?height[i]);?????????}????????return?sum;????}}

　　 动态规划空间优化：

　　
因为left和right数组中每个元素我们只使用一次，所以没必要保存整个数组，左右只保存一个值就可以。由于left和right遍历时方向不一致，left和计算时的遍历方向一致，很容易更新，而right依然要使用数组来存储，这样空间复杂度仍为O(n)。

　　
如果当前列左侧最高墙的高度比右侧最高墙的高度小，那么能装多少水由左侧决定，也就是说min变量就等于左侧最高墙的高度，反之，右侧最高墙的高度小，那么min就等于右侧最高墙的高度。那么我们

　　 在遍历过程中就可以先比较左右最高墙的高度，选两侧的较小值计算雨水量加入sum。（这里我可能说的不太清楚，如果无法理解请参照力扣中的题解：）

　　 时间复杂度O(N)，空间复杂度O(1)。

　　复制代码1234567891011121314151617181920212223242526class?Solution?{????public?int?trap(int[]?height)?{????????int?len?=?height.length;????????if(len?==?0??len?==?1)?return?0;????????int?maxLeft?=?0;????????int?maxRight?=?0;????????//加左右指针????????int?left?=?1;????????int?right?=?len?-?2;????????int?sum?=?0;????????for(int?i?=?1;?i??height[right])????????????????????sum?+=?maxRight?-?height[right];????????????????right--;????????????}????????}????????return?sum;????}}

　　
柠檬水找零（LeetCode860）

　　
在柠檬水摊上，每一杯柠檬水的售价为?5?美元。

　　
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

　　
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

　　 注意，一开始你手头没有任何零钱。

　　
如果你能给每位顾客正确找零，返回?true?，否则返回 false?。

　　 思路：尽可能有大面值找零，也就是能用10元找零就不用2个5元。是贪心算法思想的体现。

　　=?3){????????????????????five?=?five?-?3;????????????????}else{????????????????????return?false;????????????????}????????????}????????}????????return?true;????}} 数组

　　 双指针遍历：解决有序数组的问题

　　
排序数组，平方后，数组当中有多少不同的数字（相同算一个）。

　　
如果不是排序数组，可以使用hashset来保存数字的平方，重复就存不进去，那么最后就可以直接返回set的大小size即可。时间空间复杂度都是O（n)。

　　
双指针遍历 ：这里是排序数组，既然有重复，肯定是有负数，0,1这些数字。

　　 平方后两头大，中间小，可以用首尾指针共同向中间扫描，扫描时去掉重复元素，同时用一个sum来记录有多少个不同数字。

　　
时间复杂度O(N)，空间复杂度O(1)。

　　 复制代码1234567891011121314151617181920212223242526272829303132333435public?class?Solution?{????public?int?diffSquareNum(int?nums[])?{????????int?n?=?nums.length;????????if(n?==?0??nums?==?null){????????????return?0;????????}????????int?sum?=?0;????????int?left?=?0;????????int?right?=?n?-?1;????????while(left?

　　一个数据先递增再递减，找出数组不重复的个数，比如 [1, 3, 9, 1]，结果为3，不能使用额外空间，复杂度o(n)

　　与上面一题一模一样，双指针从两头向中间逼近。

　　
复制代码12345678910111213141516171819202122232425262728293031323334public?class?Solution?{????public?int?diffnum(int[]?nums){????????int?n?=?nums.length;????????if(n?==?0??nums?==?null){????????????return?0;????????}????????int?left?=?0;????????int?right?=?n?-?1;????????int?sum?=?0;????????while(left?

　　 递增数组，找出和为k的数对

　　
双指针遍历

　　 ：用头尾两个指针，分别开始遍历，两个数字和大于k时，右指针向前移动，小于k时左指针向后移动。

　　 复制代码12345678910111213141516171819public?class?Solution{????public?ArrayList?findPair(int[]?nums,int?k){????????int?n?=?nums.length;????????int?i?=?0;????????int?j?=?n?-?1;????????ArrayList?list?=?new?ArrayList();????????while(i??k){????????????????j--;????????????}else{????????????????list.add(nums[i]);????????????????list.add(nums[j]);????????????}????????}????????return?list;????}}

　　 给出一个数组nums，一个值k，找出数组中的两个下标 i，j 使得 nums[i] + nums[j] = k.

　　
这个题目跟上面一题的区别就是不是有序数组，那么解题思路就可以是

　　 排序+双指针遍历 ，时间复杂度就因为排序升为O(NlogN)。

　　
对于这个无序数组另一种解决办法是使用HashMap，数字作为键，下标作为值存入hashmap，然后遍历map查找符合条件的数对，map可以实现O(1)的查找，所以时间复杂度和空间复杂度都是O(N)。（这里需要注意，如果数组中有重复元素，那么这个方法就不能用，因为重复元素存入map时，后面的值（下标）会覆盖掉前面的值。）

　　 复制代码123456789101112131415161718//这种实现方式无法去掉重复的pair，如结果中会同时有（3,6）和（6,3）。public?class?Solution{????public?ArrayList?findPair(int[]?nums,?int?k)?{????????ArrayList?pairs?=?new?ArrayList();????????HashMap?map?=?new?HashMap();????????for?(int?i?=?0;?i??set?:?map.entrySet())?{????????????int?target?=?k?-?set.getKey();????????????//第二个判断条件是为了去除（2，2）这种情况，即同一数字即做加数又做被加数的情况tainsKey(target)?&&?!map.get(target).equals(set.getValue()))?{????????????????pairs.add(new?Pair(set.getValue(),?map.get(target)));????????????}????????}????????return?pairs;????}}

　　 滑动窗口：解决连续序列问题

　　
和为s的连续正整数序列（剑指offer57-II)

　　
输入一个正整数 target ，输出所有和为 target 的

　　 连续正整数

　　 序列（至少含有两个数）。

　　 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

　　
示例 1：

　　
输入：target = 9

　　
输出：[[2,3,4],[4,5]]

　　滑动窗口：窗口左右两端都只能向右移动，当和小于sum时，j++，和大于sum时，i++，和等于sum就记录下窗口中i —j 中的序列，然后窗口继续后移，查找下一个满足条件的序列。

　　复制代码12345678910111213141516171819202122232425262728class?Solution?{????public?int[][]?findContinuousSequence(int?target)?{????????int?i?=?1;????????int?j?=?1;????????int?sum?=?0;????????List?list?=?new?ArrayListtarget/2，那么i+i+1肯定大于target????????while(i??target){????????????????sum?-=?i;????????????????i++;????????????}else{????????????????int[]?res?=?new?int[j?-?i];????????????????for(int?z?=?i;?z?

　　某一个大文件被拆成了N个小文件，每个小文件编号从0至N-1，相应大小分别记为S(i)。给定磁盘空间为C，试实现一个函数从N个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小。

　　滑动窗口：每次记录窗口内的总和，和小于C，记录剩余空间，再窗口右端右移，和大于C，就窗口左端右移，小于C情况下比较剩余空间取最小值。

　　复制代码1234567891011121314151617181920212223242526272829public?class?Solution?{????public?int[]?findMin(int[]?s,int?c){????????int?i?=?0;????????int?j?=?0;????????int?minValue?=?Integer.MAX_VALUE;????????int?sum?=?0;????????int?left?=?0;????????int?right?=?0;????????while(j?

　　
给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata，问能否在这个字符串中找到一个长度为m的连续子串，使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。比如上面这个例子，acbd，3。 （2）

　　类似leetcode 567：

　　 分析：

　　 本题的子串需要满足长度为m，字符不重复，可以使用长为m的滑动窗口遍历字符串，窗口内每个字符都要出现一次，如果符合条件，就返回窗口起始位置。

　　 如果这里不允许使用substring,indexOf函数，可以将字符串中每个字符出现的次数存入长度为26的数组中进行比较每次数组中对应位置数量是否相等，具体可参照上面LeetCode 567题。

　　?s.length()){????????????return?-1;????????}????????for(int?i?=?0;?i?

　　有序有重复数组，给定target确定范围

　　使用滑动窗口。

　　算法题，一个有序数组，从随机一位截断，把前段放在后边，如 4 5 6 7 1 2 3求中位数

　　用排序解决，问了下一般排序算法的复杂度，O(nlogn) 扫一遍，找出分界点，O(n) 提示我还有更快的方法，那肯定只有二分了，想了好久mid的判断条件后写了个解法，给面试官叙述了一遍跑样例的过程。

　　哈希表辅助解决数组问题

　　算法：求数组的最长连续递增数列，如：4， 200， 3， 1， 100， 2。结果是1 2 3 4，也就是说顺序可以打乱。（leetcode 128）

　　
思路一：排序，然后再遍历一遍找最长连续递增数列，时间复杂度O(NlogN)。

　　
思路二：使用HashMap或者HashSet，将数组元素存入set中，然后遍历set，先找到每个序列的开头元素，即num没有num-1的情况，这时从num开始循环找num+1,记录次数，通过比较找出最大长度。时间和空间复杂度都是O（n)

　　
复制代码1234567891011121314151617181920212223//这里用set，是因为set可以自动去重，用map也不影响结果class?Solution?{????public?int?longestConsecutive(int[]?nums)?{????????if?(nums.length?==?0)?return?0;????????HashSet?set?=?new?HashSet();????????for(int?value?:?nums)????????????set.add(value);?????????int?longestLength?=?0;????????for?(int?num:?set)?{????????????if?(!set.contains(num?-?1)){????????????????int?currentNum?=?num;????????????????int?currentLength?=?1;????????????????while?(set.contains(currentNum?+?1)){????????????????????currentNum?+=?1;????????????????????currentLength?+=?1;????????????????}????????????????longestLength?=?Math.max(longestLength,currentLength);????????????}????????}????????return?longestLength;????}}

　　一个无序数组，从小到大找到第一个缺的数，比如[8 2 4 3 6 9 7 11 12],第一个缺的就是5 （2）

　　1.排序，时间复杂度O(NlogN)

　　2.用数组作为哈希表，将数字i放入数组中的i索引处，然后找中间没有存入数字的位置。时间和空间复杂度都是O(N)

　　复制代码1234567891011121314151617181920212223public??class?Solution?{????public?int?findLost(int[]?nums){????????int?min?=?nums[0];????????int?max?=?nums[0];????????for(int?value?:?nums){????????????min?=?Math.min(min,value);????????????max?=?Math.max(max,value);????????}????????int[]?res?=?new?int[max?-?min?+?1];????????for(int?i?=?0;?i?

　　输出给定数字下一个比它大的数字，比如输入：1234， 输出 1243。

　　
首先从后往前遍历找到一个数字nums[i]比num[i+1]小，也就是找到递减到递增的转折点，然后再与递减序列中最小的大于num[i]的数字交换，这样交换完之后后面仍然是递减序列，将其转换为递增序列，这样可以保证数字增大，并且增大的幅度最小。

　　复制代码1234567891011121314151617181920212223242526272829303132333435class?Solution?{????public?void?nextPermutation(int[]?nums)?{????????//从倒数第二个数字开始比较????????int?i?=?nums.length?-?2;????????//找nums[i]?=?nums[j]){????????????????j--;????????????}?????????????swap(nums,i,j);????????}????????reverse(nums,i?+?1);????}?????public?void?swap(int[]?nums,int?i,?int?j){????????int?temp?=?nums[i];????????nums[i]?=?nums[j];????????nums[j]?=?temp;????}?????public?void?reverse(int[]?nums,int?start){????????int?j?=?nums.length?-?1;????????int?i?=?start;????????//因为是递减序列，所以可以这样交换成递增的????????while(i?

　　算法题(leetcode55题)：给一个数组，例如[1,2,3,4,5]，a[i]表示在该位置可以向前行走的最大距离，判断是否可以到达数组的最后一个元素

　　思路：

　　每次走最大的距离，如果能超过末尾元素，说明只要调小步伐就一定可以达到最后位置。

　　复制代码123456789101112131415public?class?Solution?{????public?boolean?canJump(int[]?nums)?{????????int?n?=?nums.length;????????int?rightmost?=?0;????????for?(int?i?=?0;?i?=?n?-?1)?{????????????????????return?true;????????????????}????????????}????????}????????return?false;????}}

　　AB两个排序数组，原地合并数组。（A当中穿插一些无效数字怎么处理？）

　　思路：因为要原地合并数组，如果从前往后遍历，数组原来的值会被覆盖，所以只能从后往前遍历，将值从后往前存入。存入时比较当前两个指针指向的数字大小，选较大的存入，然后往前移动指针。

　　（有无效数字的情况楼主没有想到好的解决办法，小伙伴们如果有思路请在评论区解答，感谢！）

　　=?0){????????????if(i?=?A[i]){????????????????A[k--]?=?B[j--];????????????}else?{????????????????A[k--]?=?A[i--];????????????}????????}????}} 排序相关

　　快排（3)

　　 复制代码1234567891011121314151617181920212223242526public?void?quickSort(int[]?arr,int?L,int?R){????if?(arr.length?==?0)?return;????int?i?=?L;????int?j?=?R;????int?key?=?arr[(i?+?j)/2];????while?(i??key)????????????j--;????????if?(i?

　　桶排序

　　
（3）桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布 ，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

　　
算法描述：

　　设置一个定量的数组当作空桶； 遍历输入数据，并且把数据一个一个放到对应的桶里去； 对每个不是空的桶进行排序； 从不是空的桶里把排好序的数据拼接起来。

　　复制代码1234567891011121314151617181920212223242526272829303132public?class?Solution?{????public?ArrayList?bucketSort(int[]?scores){??????//先确定最大最小值，来确定范围??????int?max?=?Integer.MIN_VALUE;??????int?min?=?Integer.MAX_VALUE;??????for(int?i?=?0;?i??list?=?new?ArrayList(bucketNum);??????for(int?i?=?0;?i?());??????}?????????????//将每个元素放入桶??????for(int?i?=?0;?i?

　　数组中第K大的数（LeetCode215题）

　　首先想到最简单的排序，然后返回第k大的元素，时间复杂度O(NlogN)。

　　
快排的patition思想：时间复杂度O（n)，空间复杂度O(1)

　　复制代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051public?class?Solution?{????public?int?findKthLargest(int[]?nums,?int?k)?{????????int?len?=?nums.length;????????int?left?=?0;????????int?right?=?len?-?1;????????//?转换一下，第?k?大元素的索引是?len?-?k????????int?target?=?len?-?k;?????????while?(true)?{????????????int?index?=?partition(nums,?left,?right);????????????if?(index?==?target)?{????????????????return?nums[index];????????????}?else?if?(index?=?nums[left]?????*/????public?int?partition(int[]?nums,?int?left,?int?right)?{????????int?pivot?=?nums[left];????????int?j?=?left;????????for?(int?i?=?left?+?1;?i?=?pivot????????swap(nums,?j,?left);????????//?交换以后?[left,?j?-?1]?=?pivot????????return?j;????}?????private?void?swap(int[]?nums,?int?index1,?int?index2)?{????????int?temp?=?nums[index1];????????nums[index1]?=?nums[index2];????????nums[index2]?=?temp;????}}

　　
top k，返回前K大的元素

　　这里可以使用和上题一样的快排patition。

　　也可以用堆排序，可以取前k个元素构造小根堆，然后遍历后面的元素，如果读取到的元素比堆顶下，直接丢弃，如果比堆顶大，就替换掉堆顶元素，然后调整堆。时间复杂度O(NlogK)。（堆实现参考下一题）

　　复制代码123456789101112131415161718192021222324252627282930313233343536373839404142public?class?Solution?{????public?ArrayList?topK(int[]?nums){????????if(nums.length??list?=?new?ArrayList();????????for(int?i?=?target;i??pivot){???????????????j++;???????????????swap(nums,i,j);???????????}???????}???????swap(nums,left,j);???????return?j;????}????public?void?swap(int?nums,int?i,int?j){????????int?temp?=?nums[i];????????nums[i]?=?nums[j];????????nums[j]?=temp;????}}

　　10亿个数字，取最小的100个数

　　(说思路 最大堆， partition 两者的时间复杂度，写伪代码)

　　1.最大堆：先取出前100个数，维护一个100个数的最大堆，遍历一遍剩余的元素，在此过程中维护这个最大堆就可以了。

　　具体步骤如下：

　　step1：取前m个元素（例如m=100），建立一个大根堆。保持一个大根堆得性质的步骤，运行时间为O（logm);建立一个大根堆运行时间为mO(logm）=O(m logm);

　　step2:顺序读取后续元素，直到结束。每次读取一个元素，如果该元素比堆顶元素大，直接丢弃；如果小于堆顶元素，则用该元素替换堆顶元素，然后保持最大堆性质。最坏情况是每次都需要替换掉堆顶的最大元素，因此需要维护堆的代价为(N-m)O(lgm); 最后这个堆中的元素就是前最小的100个。时间复杂度为O(N lgm）。

　　时间复杂度为O(10亿*lg100)。

　　首先构造大根堆： 堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：

　　 (0

　　① array[i]

　　= array[2*i + 2]； 称为大根堆；

　　n个节点的完全二叉树array[0，...，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆。

　　对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。

　　=?0;?i--)?{????????adjustDownToUp(array,?i,?array.length);????}????return?array;}//将元素array[k]自下往上逐步调整树形结构private?void?adjustDownToUp(int[]?array,?int?k,?int?length)?{????int?temp?=?array[k];????for?(int?i?=?2?*?k?+?1;?i?=左右子女中关键字较大者，调整结束????????????break;????????}?else?{???//根节点?

　　 堆排序(大根堆)：

　　①将存放在array[0，...，n-1]中的n个元素建成初始堆；

　　②将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；

　　③但此时堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再重复第②③步，直到堆中仅剩下一个元素为止。

　　堆排序算法的性能分析：

　　空间复杂度:o(1)；

　　时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);

　　稳定性：不稳定

　　?1;?i--)?{????????int?temp?=?array[0];??//将堆顶元素和堆底元素交换，即得到当前最大元素正确的排序位置????????array[0]?=?array[i];????????array[i]?=?temp;????????adjustDownToUp(array,?0,?i);??//整理，将剩余的元素整理成堆????}????return?array;}

　　本题中：构造完堆之后将新的元素与大根堆的堆顶元素比较，如果新元素比堆顶元素大，直接舍弃，如果小就跟堆顶元素交换，然后调整大根堆。

　　复制代码12345678910111213public?int[]?findMin(int[]?array,int[]?all){????array?=?buildMaxHeap(array);????//前面100个数字（0-99号）已经取出了????for(int?i?=?100;i?=?array[0]){????????????continue;????????}?else?{????????????array[0]?=?all[i];????????????adjustDownToUp(array,0,array.length);????????}????????}????return?array;}

　　 2.快排划分的思想：

　　每次分割之后只考虑比轴小的一部分，直到比轴小的一部分数量在100多个的时候，采用传统排序算法排序，取前100个。

　　step1：递归对所有数据分成[a,b)，(b,d]两个区间，[a,b)区间内的数都是小于(b,d]区间内的数。

　　step2：对[a,b)重复 step1操作，直到最左边的区间个数小于100个。注意(b,d]区间不用划分

　　step3：返回上一个区间 ，并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分，分为[a2,b2)，(b2,d2]两个区间，取(a2,b2]区间。如果个数不够，继续 step3操作，如果个数超过100的就重复 step1操作，直到最后右边只有100个数为止。

　　复杂度为O(10亿*100) 算法：手写jdk中的优先级队列 PriorityQueue（最小堆）

　　参照上题中堆的实现。

　　栈，队列和链表最大栈（最小栈）

　　
复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162使用辅助栈：public?class?MaxStack{????private?Stack?stack;????private?Stack?helper;????public?MaxStack(){????????stack?=?new?Stack();????????helper?=?new?Stack();????}????public?void?push(int?x)?{????????if(helper.isEmpty()??helper.peek()??stack;????public?MaxStack(){????????stack?=?new?Stack();????}????int?max?=?Integer.MIN_VALUE;????public?void?push(int?x){????????if(max?

　　两个栈实现一个队列

　　复制代码123456789101112131415161718192021222324252627282930public?class?StackToList{????private?Stack?stack;????private?Stack?helper;?????????public?StackToList{????????stack?=?new?Stack();????????helper?=?new?helper();????}????public?void?push(int?x){????????stack.push(x);????}????public?Integer?poll()?{????????if(stack.isEmpty()?&&?helper.isEmpty())????????????throw?new?RuntimeException(队列为空);????????dataRemove();????????return?helper.pop();????}????public?Integer?peek()?{????????if(stack.isEmpty()?&&?helper.isEmpty())????????????throw?new?RuntimeException(队列为空);????????dataRemove();????????return?helper.peek();????}????public?void?dataRemove(){???????if(helper.isEmpty()){????????????while(!stack.isEmpty())????????????????helper.push(stack.pop());????????}????}}

　　
两个队列实现一个栈：

　　复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253/**?????*?@Description:?仅用队列来实现栈?????*?采用两个队列，一个数据队列queue?一个辅助队列?help?????*?入队时全部入队queue?出队时，将queue队列中数据入队help?将最后一个数?返回?并queue指针和help交换?????*/????public?static?class?QueueToStack{????????private?Queue?queue;????????private?Queue?help;????????public?QueueToStack(){????????????queue?=?new?LinkedList();????????????help?=?new?LinkedList1){????????????????help.add(queue.poll());????????????}????????????int?temp=queue.poll();????????????help.add(temp);????????????swap();????????????return?temp;????????}??????????private?void?swap()?{????????????Queue?temp?=?queue;????????????queue?=?help;????????????help?=?temp;????????}????}

　　链表实现一个栈

　　复制代码1234567891011121314151617181920212223242526public?class?ListNode{????int?val;????ListNode?next;????ListNode(int?val){????????this.val?=val;????}}public?class?ListToStack{????public?ListToStack(){????????ListNode?head;????}????public?void?push(int?x){????????ListNode?node?=?new?ListNode(x);????????node.next?=?head.next;????????head.next?=?node;????}????public?int?pop(){????????ListNode?node?=?head.next;????????head.next?=?node.next;????????node.next?=?null;????????return?node.val;????}????public?int?peek(){????????return?head.next.val;????}}

　　两个链表，可能相交，找出相交的节点，给出证明（2)

　　
1.若两个单链表一个为有环,一个无环. 那么肯定不能相交.

　　2.若二者都没有环, 问题就转化为

　　 两个无环单链表是否相交,是否能找到第一个相交的节点，方法就是快慢指针。

　　3.若二者都有环,那么问题变成了两个有环单链表是否相交.

　　第一,先找到二者是否相交.

　　第二,若相交则需要遍历一遍找到相交点.

　　如果无环：问题转化为如何判断两个无环链表是否相交？

　　要想判断是否相交，肯定要看是否能找到相交的点，如果能让两个指针同时走到相交点，也就可以确定两个链表相交。因为相交后两个链表到终点的距离相等，那么只要两个指针能够消除两个链表之间的长度差就可以到达终点的距离相等。假设链表A比B长，pB到达结尾后指向headA，然后继续向前遍历，当pA到达结尾后指向headB，此时两者的长度差就消除了。继续遍历如果两者指向同一节点，返回节点，如果两者都走到结尾依然没有相交，就返回null。

　　
复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344//无环的情况public?class?ListNode?{????int?val;????ListNode?next;????ListNode(int?val){????????this.val?=?val;????????next?=?null;????}}?public?class?Solution?{????public?ListNode?getListNode(ListNode?headA,ListNode?headB)?{????????if(headA?==?null??headB?==?null){????????????return?null;????????}????????ListNode?pA?=?headA,pB?=?headB;????????while(pA?!=?pB){????????????if(pA?==?null){????????????????pA?=?headB;????????????}else{????????????????pA?=?pA.next;????????????}????????????if(pB?==?null){????????????????pB?=?headA;????????????}else{????????????????pB?=?pB.next;????????????}????????}????????return?pA;????}}简化版：public?class?Solution?{????public?ListNode?getIntersectionNode(ListNode?headA,?ListNode?headB)?{????????if?(headA?==?null??headB?==?null)?return?null;????????ListNode?pA?=?headA,?pB?=?headB;????????//如果不相交，pA=pB=null????????while?(pA?!=?pB)?{????????????pA?=?pA?==?null???headB?:?pA.next;????????????pB?=?pB?==?null???headA?:?pB.next;????????}????????return?pA;????}}

　　如果有环，就转化为如何判断两个有环链表是否相交？

　　两个有环链表相交分为两种情况，一种是两个链表在进入环之前相交，另一种是两个链表在环内相交，如果不是在同一个节点进入，就是两个入口在两个节点。

　　第一种情况：可以将环在环的入口处断开，这样就与无环链表相交一样，可以根据无环链表的方法判断；

　　第二种情况：两者相交于环内，而且入环口不同。pA的入口节点（标记位loopA），pB的入环口标记为loopB,当他们都遍历一圈停在自己的入口节点时，pA往后遍历，pB不动，pA回到loopA之前，一定会碰到pB,如果碰不到，说明两者不在一个环里。

　　如果两种都不是，则是没有相交。

　　找有环链表的入口节点：

　　快慢指针：设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。

　　证明结论1：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。

　　证明结论2：

　　设： 链表头到环入口长度为--a ；环入口到相遇点长度为--b ；相遇点到环入口长度为--c

　　=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。

　　慢指针路程=a+b

　　快指针走的路程是慢指针的两倍，所以： （a+b）*2=a+(b+c)k+b

　　化简可得：

　　=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

　　复制代码1234567891011121314151617181920212223242526272829pulic?class?ListNode{????int?val;????ListNode?next?=?null;????ListNode(int?val){????????this.val?=?val;????}}public?class?Solution?{????public?ListNode?EntryNodeOfLoop(ListNode?pHead){????????ListNode?fast?=?pHead;????????ListNode?slow?=?pHead;????????if(fast?==?null??fast.next?==?null){????????????return?null;????????}????????while(fast?!=?null?&&?fast.next?!=?null){????????????fast?=?fast.next.next;????????????slow?=?slow.next;????????????if(fast?==?slow){????????????????break;????????????}????????}????????slow?=?pHead;????????while(fast?!=?slow){????????????fast?=?fast.next;????????????slow?=?slow.next;????????}????????return?fast;????}}

　　反转链表升级版（每k个反转一下）（4）

　　普通版：

　　方法一:递归

　　复制代码1234567891011121314151617181920public?class?Listnode{????int?val;????ListNode?next;????ListNode?pre;????ListNode?(int?val){????????this.val?=?val;????}}//递归public?class?Solution{????public?ListNode?revoseList(ListNode?head){????????if(head?==?null??head.next?==?null){????????????return?head;????????}????????ListNode?cur?=?revoseList(head.next);????????head.next.next?=?head;????????head.next?=?null;????????return?cur;????}}

　　方法二：双指针迭代

　　复制代码12345678910111213141516171819public?class?Solution{????public?ListNode?revoseList(ListNode?head){????????if(head?==?null??head.next?==?null){????????????return?head;????????}????????ListNode?pre?=?null;????????ListNode?cur?=?head;????????ListNode?temp?=?null;????????while(cur?!=?null){????????????//标记下一个节点，以免丢失????????????temp?=?cur.next;????????????//实现反转????????????cur.next?=?pre;????????????pre?=?cur;????????????cur?=?temp;????????}????????return?pre;????}}

　　K个一组反转链表（LeetCode25题） ：

　　复制代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950/**?*?Definition?for?singly-linked?list.?*?public?class?ListNode?{?*?????int?val;?*?????ListNode?next;?*?????ListNode(int?x)?{?val?=?x;?}?*?}?*/class?Solution?{????public?ListNode?reverseKGroup(ListNode?head,?int?k)?{????????//定义一个头指针，用来将后面所有节点统一处理????????ListNode?dum?=?new?ListNode();????????dum.next?=?head;????????//用来标记每一次反转部分的前一个结点????????ListNode?pre?=?dum;????????//运动指针，扫描要反转的部分????????ListNode?end?=?dum;?????????while(end.next?!=?null){????????????//每次扫描完要反转的部分，如果end为空说明达到尾部，直接break????????????for(int?i?=?0;?i?

　　leetcode 链表求和

　　给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。

　　示例：

　　 2)，即617 + 295

　　 9，即912

　　（如果链表存储数据的顺序反过来怎么加？这个楼主不会，大家有思路请在评论区交流，十分感谢！）

　　 复制代码123456789101112131415161718192021222324252627/**?*?Definition?for?singly-linked?list.?*?public?class?ListNode?{?*?????int?val;?*?????ListNode?next;?*?????ListNode(int?x)?{?val?=?x;?}?*?}?*/class?Solution?{????public?ListNode?addTwoNumbers(ListNode?l1,?ListNode?l2)?{????????ListNode?head?=?new?ListNode(0);????????ListNode?cur?=?head;????????int?carry?=?0;//用以计算进位????????//只要有一个不为空或者最后有进位都要继续循环????????while(l1?!=?null??l2?!=?null??carry?!=?0){????????????int?num1?=?l1?==?null???0?:?l1.val;????????????int?num2?=?l2?==?null???0?:?l2.val;????????????int?sum?=?num1?+?num2?+?carry;????????????carry?=?sum?/?10;????????????cur.next?=?new?ListNode(sum?%?10);????????????if(l1?!=?null)?l1?=?l1.next;????????????if(l2?!=?null)?l2?=?l2.next;????????????cur?=?cur.next;????????}????????return?head.next;????}} 二叉树

　　二叉树的前序遍历非递归

　　
复制代码123456789101112131415161718192021222324252627282930public?class?TreeNode{????int?val;????TreeNode?left;????TreeNode?right;????TreeNode(int?val){????????this.val?=?val;????}}//非递归public?void?preOrder(TreeNode?root){????if(root?==?null)?return;????Stack?stack?=?new?Stack();????stack.push(root);????while(!stack.isEmpty()){????????TreeNode?node?=?stack.pop();????????System.out.print(node.val);????????//因为栈是先进后出，所以先压右孩子，再压左孩子????????if(node.right?!=?null)????????????stack.push(node.right);????????if(node.left?!=?null)????????????stack.push(node.left);????}?}//递归public?void?preOrder(TreeNode?root){????if(root?==?null)?return;????System.out.print(root.val);????preOrder(root.left);????preOrder(root.right);}

　　二叉树的后序遍历非递归(2)

　　由于压栈顺序是

　　从上而下，先左后右，出栈时就是从下而上，先右后左，这时可以用一个辅助栈，将弹出的值压入栈中，最后统一弹出，顺序就是后序遍历的先左后右，从下而上。（也可以用LinKedList，弹出后加入链表头，这样也可以逆序）

　　复制代码12345678910111213141516public?void?postOrder(TreeNode?root){????if(root?==?null)?return;????Stack?s1?=?new?Stack();????Stack?s2?=?new?Stack();????s1.push(root);????while(!s1.isEmpty()){????????TreeNode?node?=?s1.pop();????????s2.push(node);????????if(node.left?!=?null)???????????s1.push(node.left);???????if(node.right?!=?null)???????????s1.push(node.right);????}????while(!s2.isEmpty())????????System.out.print(s2.pop().val?+??);}

　　
中序遍历非递归

　　复制代码12345678910111213141516171819//中序遍历非递归class?Solution?{????public?List?inorderTraversal(TreeNode?root)?{????????Stack?stack?=?new?Stack();????????TreeNode?p?=root;????????ArrayList?list?=?new?ArrayList();????????while(p?!=?null??!stack.isEmpty()){????????????//一直走到最左边的左孩子????????????while(p?!=?null){????????????????stack.push(p);????????????????p?=?p.left;????????????}????????????p?=?stack.pop();????????????list.add(p.val);????????????p?=?p.right;????????}????????return?list;????}}

　　从上往下打印二叉树（层序遍历）（2)

　　与后序遍历类似，可使用队列，将左右节点节点先后加入队列尾，每次从队列头取出节点进入输出链表。这样可以保证每次取出的元素都是本层现存的第一个元素。

　　复制代码1234567891011121314151617181920212223242526272829public?class?TreeNode?{????int?val;????TreeNode?left?=?null;????TreeNode?right?=?null;????public?TreeNode(int?val){????????this.val?=?val;????}}?public?class?Solution?{????public?ArrayList?PrintFromTopToBottom(TreeNode?root)?{????????ArrayList?result?=?new?ArrayList();????????if(root?==?null)????????????return?result;????????LinkedList?queue?=?new?LinkedList();????????queue.add(root);????????while(!queue.isEmpty()){????????????TreeNode?node?=?queue.poll();????????????result.add(node.val);????????????if(node.left?!=?null){????????????????queue.add(node.left);????????????}????????????if(node.right?!=?null){????????????????queue.add(node.right);????????????}????????}????????return?result;????}}

　　蛇形遍历二叉树(2)

　　与层序遍历的区别是当层数为奇数就从左往右遍历，层数是偶数，就从右往左。

　　复制代码1234567891011121314151617181920212223242526272829303132public?class?Solution?{????public?ArrayList?PrintFromTopToBottom(TreeNode?root)?{????????ArrayList?result?=?new?ArrayList();????????if(root?==?null)????????????return?result;????????LinkedList?queue?=?new?LinkedList();????????queue.add(root);????????int?level?=?1;//认为根节点在第一层????????while(!queue.isEmpty()){????????????TreeNode?node?=?queue.poll();????????????result.add(node.val);????????????level++;????????????if(level?%?2?==?1){????????????????if(node.left?!=?null){????????????????????queue.add(node.left);????????????????}????????????????if(node.right?!=?null){????????????????????queue.add(node.right);????????????????}????????????}else?{????????????????if(node.right?!=?null){????????????????????queue.add(node.right);????????????????}????????????????if(node.left?!=?null){????????????????????queue.add(node.left);????????????????}????????????}????????????????????}????????return?result;????}}

　　二叉树右视图（2）

　　就是找层序遍历每层最后一个节点。

　　复制代码12345678910111213141516171819202122232425262728293031323334353637/**?*?Definition?for?a?binary?tree?node.?*?public?class?TreeNode?{?*?????int?val;?*?????TreeNode?left;?*?????TreeNode?right;?*?????TreeNode(int?x)?{?val?=?x;?}?*?}?*/class?Solution?{????public?List?rightSideView(TreeNode?root)?{????????ArrayList?res?=?new?ArrayList();????????if(root?==?null)?return?res;????????int?curCount?=?1;????????int?nextCount?=?0;????????LinkedList?list?=?new?LinkedList();????????list.add(root);????????while(!list.isEmpty()){????????????TreeNode?node?=?list.poll();????????????curCount?--;????????????if(node.left?!=?null){????????????????list.add(node.left);????????????????nextCount++;????????????}????????????if(node.right?!=?null){????????????????list.add(node.right);????????????????nextCount++;????????????}????????????if(curCount?==?0){????????????????res.add(node.val);????????????????curCount?=?nextCount;????????????????nextCount?=?0;????????????}????????}????????return?res;????}}

　　二叉树各层节点数，递归、非递归，时间、空间复杂度

　　思路：借助队列实现层序遍历，在遍历的过程中，level记录当前层数，curCount当前层的节点数，nextCount下一层的节点数。每次弹出节点，将当前层节点减一，然后将当前节点的左右子节点加入队列，同时计数。当前层的节点数等于0时，说明这一层遍历完了，同时记录的下一层节点数就是下一层总的节点，直接保存。遍历到队列为空为止。

　　复制代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354//非递归，时间复杂度O(N),空间复杂度O(N)public?Map?levelNodeCount(TreeNode?root){????HashMap?map?=?new?HashMap();????if(root?==?null)?return?map;????int?level?=?1;????int?curCount?=?1;????int?nextCount?=?0;????map.put(level,curCount);????LinkedList?list?=?new?LinkedList();????list.add(root);????while(!list.isEmpty()){????????TreeNode?node?=?list.poll();????????curCount--;????????if(node.left?!=?null){????????????list.add(node.left);????????????nextCount++;????????}????????if(node.right?!=?null){????????????list.add(node.right);????????????nextCount++;????????}?????????if(curCount?==?0){?????????????level++;?????????????map.put(level,nextCount);?????????????curCount?=?nextCount;?????????????nextCout?=?0;?????????}???????}????return?map;}递归：时间复杂度O(N),空间复杂度O(N)这里保存了每一层的每一个节点class?Solution?{????private?List?res?=?new?ArrayList();????public?List?levelOrder(TreeNode?root)?{????????if(root?==?null)????????????return?res;????????helper(root,0);????????return?res;????}????public?void?helper(TreeNode?root,int?level){????????//说明level已经比现存的层数(res.size()?-?1)多了，需要新建一个新的????????if(res.size()?==?level){????????????res.add(new?ArrayList());????????}????????//存入当前层的列表里，递归过程中每次都会往一个列表里面加入数字，每次都????????//加到不同的列表里。????????res.get(level).add(root.val);????????if(root.left?!=?null)????????????helper(root.left,level?+?1);????????if(root.right?!=?null)????????????helper(root.right,level?+?1);??????}}

　　二叉搜索树的第K大的节点

　　
二叉搜索树（二叉排序树）满足：根节点大于左子树，小于右子树。那么二叉树的中序遍历序列就是一个递增序列 。

　　为方便了找第K大的节点，我们可以调换左右子树的遍历顺序，这样遍历序列是一个递减序列，这样遍历到第K个元素就是我们要找的第K大的节点。

　　复制代码1234567891011121314151617181920212223242526272829303132333435363738//迭代：class?Solution?{????public?int?kthLargest(TreeNode?root,?int?k)?{????????Stack?stack?=?new?Stack();????????TreeNode?p?=?root;????????int?count?=?0;????????while(p?!=?null??!stack.isEmpty()){????????????while(p?!=?null){????????????????stack.push(p);????????????????p?=?p.right;????????????}????????????p?=?stack.pop();????????????count++;????????????if(count?==?k){????????????????return?p.val;????????????}????????????p?=?p.left;????????}????????return?0;????}}//递归class?Solution?{????int?res,index;????public?int?kthLargest(TreeNode?root,?int?k)?{????????index?=?k;????????dfs(root);????????return?res;????}????public?void?dfs(TreeNode?root){????????if(root?==?null)?return;????????dfs(root.right);????????if(index?==?0)?return;????????index--;????????if(index?==?0)?res?=?root.val;????????dfs(root.left);????}}

　　求完全二叉树的节点个数，小于O(n)，并分析复杂度

　　完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2^h个节点。

　　分析：首先统计二叉树左右子树的层数，有以下两种情况：

　　 left == right。这说明，左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是2^left - 1，加上当前这个root节点，则正好是2^left。再对右子树进行递归统计。

　　 left != right。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点+root节点，总数为2^right。再对左子树进行递归查找。

　　时间复杂度为O(logN*logN)

　　复制代码12345678910111213141516171819202122class?Solution?{????public?int?countNodes(TreeNode?root)?{????????if(root?==?null)????????????return?0;????????int?left?=?countlevel(root.left);????????int?right?=?countlevel(root.right);????????if(left?==?right){????????????//移位运算，1向左移动left次，相当于1*2^n????????????return?countNodes(root.right)?+?(1

　　编程题：求二叉树根节点到叶子结点的路径和的最小值（leetcode）

　　递归：只有左子树，就只计算左子树，只有右子树，就只计算右子树，两个都有，就计算左右子树取最小值。

　　复制代码12345678910public?int?minPath(TreeNode?root){????if(root?==?null)?return?0;????if(root.left?!=?null?&&?root.right?==?null){????????return?1+minPath(root.left);????}????if(root.left?==?null?&&?root.right?!=?null){????????return?1?+?minPath(root.right);????}????return?1?+?Math.min(minPath(root.left),minPath(root.right));}

　　二叉树中的最大路径和 leetcode 124

　　给定一个非空二叉树，返回其最大路径和。

　　
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列 。该路径至少包含一个节点，且不一定经过根节点。

　　思路：递归计算单边值，如果单边值小于0就不算，单边值大于0就加到总的路径和里面。

　　单边最大和等于Math.max(root, root+left, root+right)。计算单边最大和的过程中记录总的最大和。

　　
right?作为路径与历史最大值做比较????????max?=?Math.max(max,?root.val?+?leftMax?+?rightMax);????????//?返回经过root的单边最大分支给上游????????return?root.val?+?Math.max(leftMax,?rightMax);????}???

　　写代码： 二叉树的最近公共祖先 leetcode 236 稍有不同，原题的2个节点，面试是多个节点，算法的时间复杂度 (2)

　　给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

　　最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

　　两个节点 :递归

　　当我们用递归去做这个题时不要被题目误导，应该要明确一点

　　这个函数的功能有三个：给定两个节点 p 和 q

　　如果 p 和 q 都存在，则返回它们的公共祖先；

　　如果只存在一个，则返回存在的一个；

　　如果 p 和 q 都不存在，则返回NULL

　　本题说给定的两个节点都存在，那自然还是能用上面的函数来解决

　　
具体思路：

　　（1） 如果当前结点 root 等于NULL，则直接返回NULL

　　（2） 如果root 等于 p 或者 q ，那这棵树一定返回 p 或者 q

　　（3） 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 left 和 right 表示

　　（4） 此时若left为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left

　　（5） 如果 left 和 right 都非空，因为只给了 p 和 q 两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先

　　（6） 如果 left 和right 都为空，则返回空（其实已经包含在前面的情况中了）

　　时间复杂度是O(n)：每个结点最多遍历一次，空间复杂度是O(n)：需要系统栈空间

　　复制代码123456789101112class?Solution?{????public?TreeNode?lowestCommonAncestor(TreeNode?root,?TreeNode?p,?TreeNode?q)?{????????if(root?==?null)?return?null;????????if(root?==?p??root?==?q)?return?root;????????TreeNode?left?=?lowestCommonAncestor(root.left,p,q);????????TreeNode?right?=?lowestCommonAncestor(root.right,p,q);????????if(left?==?null)?return?right;????????if(right?==?null)?return?left;????????if(right?!=?null?&&?left?!=?null)?return?root;????????return?null;????}}

　　多个节点的情况类似，多加一个判断条件就好了，依然是看左右子树是否存在某个节点。

　　路径总和 leetcode 112及其延伸

　　给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

　　
复制代码123456789101112131415161718192021222324252627282930313233343536373839404142//递归class?Solution?{????public?boolean?hasPathSum(TreeNode?root,?int?sum)?{????????if(root?==?null)?return?false;????????sum?-=?root.val;????????if(root.left?==?null?&&?root.right?==?null){????????????return?sum==0;????????}else{????????????return?(hasPathSum(root.left,sum)??hasPathSum(root.right,sum));????????}????}}//迭代：需要同时记录当前剩余的sum和当前节点class?Solution?{????public?boolean?hasPathSum(TreeNode?root,?int?sum)?{????????if(root?==?null)?return?false;????????Stack?nodeStack?=?new?Stack();????????Stack?numStack?=?new?Stack();?????????nodeStack.push(root);????????numStack.push(sum?-?root.val);?????????while(!nodeStack.isEmpty()){????????????TreeNode?node?=?nodeStack.pop();????????????Integer?value?=?numStack.pop();?????????????????????????if(node.left?==?null?&&?node.right?==?null?&&?value?==?0){????????????????return?true;????????????}?????????????if(node.left?!=?null){????????????????nodeStack.push(node.left);????????????????numStack.push(value?-?node.left.val);????????????}????????????if(node.right?!=?null){????????????????nodeStack.push(node.right);????????????????numStack.push(value?-?node.right.val);????????????}????????}????????return?false;????}}

　　延伸：（LeetCode113题）

　　给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

　　递归+回溯：

　　复制代码123456789101112131415161718192021222324252627282930class?Solution?{????List?res;????public?List?pathSum(TreeNode?root,?int?sum)?{????????res?=?new?ArrayList();????????if(root?==?null)????????????return?res;????????backTrack(root,?sum,?0,?new?ArrayList());????????return?res;????}?????private?void?backTrack(TreeNode?x,?int?sum,?int?curSum,?List?vals){????????vals.add(x.val);????????curSum?+=?x.val;????????if(x.left?==?null?&&?x.right?==?null){????????????if(curSum?==?sum){????????????????res.add(new?ArrayList(vals));????????????}????????????//到达叶子节点后，无论是否符合要求都要????????????//回退到上一个节点，看上一个节点的右子树是否符合要求????????????vals.remove(vals.size()?-?1);????????????return;????????}????????if(x.left?!=?null)????????????backTrack(x.left,?sum,?curSum,?vals);????????if(x.right?!=?null)????????????backTrack(x.right,?sum,?curSum,?vals);???????//回溯，结果不同就回溯到上一个节点判断另一条路可不可以????????vals.remove(vals.size()?-?1);????}}

　　重建二叉树

　　 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

　　复制代码123456789101112131415161718192021222324252627class?Solution?{????private?HashMap?map?=?new?HashMap();????private?int[]?preorder;????public?TreeNode?buildTree(int[]?preorder,?int[]?inorder)?{????????int?length?=?preorder.length;????????this.preorder?=?preorder;????????for(int?i?=?0;i??inR){????????????return?null;????????}????????????????????int?privot?=?preorder[preL];????????TreeNode?root?=?new?TreeNode(privot);?????????int?privotIndex?=?map.get(privot);?????????root.left?=?buildTree(preL?+?1,preL?+?(privotIndex?-?inL),inL,privotIndex?-1);????????root.right?=?buildTree(preL?+?(privotIndex?-?inL)?+?1,preR,privotIndex?+?1,inR);????????return?root;????}}