leetcode 从一个string到另一个string最少需要string找到int多少次修改
点击联系发帖人
时间：2017-11-06 06:48
当前位置： >>
leetcode-solution
LeetCode题解Table of Contents1.
Introduction 2.
Remove Element ii.
Remove Duplicates from Sorted Array iii.
Plus One iv.
Pascal's Triangle v.
Merge Sorted Array vi.
Find Minimum in Rotated Sorted Array viii.
Largest Rectangle in Histogram ix.
Maximal Rectangle x.
Palindrome Number xi.
Search a 2D Matrix xii.
Search for a Range xiii.
Search Insert Position xiv.
Find Peak Element 3.
Bit Manipulation i.
Missing Number ii.
Power of Two iii.
Number of 1 Bits 4.
Depth of Binary Tree ii.
Construct Binary Tree iii.
Binary Tree Level Order Traversal iv.
Symmetric Tree v.
Same Tree vi.
Balanced Binary Tree vii.
Path Sum viii.
Binary Tree Depth Order Traversal ix.
Populating Next Right Pointers in Each Node x.
Convert Sorted List/Array to Binary Search Tree xi.
Path Sum II xii.
Flatten Binary Tree to Linked List xiii.
Validate Binary Search Tree xiv.
Recover Binary Search Tree xv.
Binary Tree Path xvi.
Sum Root to Leaf Numbers 5.
Dynamic Programming i.
Best Time To Buy And Sell Stock ii.
Unique Paths iii.
Maximum Subarray iv.
Climbing Stairs 2 LeetCode题解v.
Triangle vi.
Unique Binary Search Trees vii.
Perfect Squares 6.
Backtracking i.
Combination ii.
Subsets iii.
Permutation 7.
Jump Game ii.
Gas Station iii.
Word Break 8.
Linked List i.
Linked List Cycle ii.
Remove Duplicates from Sorted List iii.
Merge Sorted Lists iv.
Reverse Linked List v.
Swap Nodes in Pairs vi.
Sort List vii.
Rotate List viii.
Reorder List ix.
Partition List x.
Add Two Numbers xi.
Copy List with Random Pointer 9.
Reverse Integer 10.
Add Binary ii.
Basic Calculator II3 LeetCode题解前言首先声明，我和张晓都不是算法牛人，确切的说应该是算法的门外汉，小白一个。所以我们为了撬开算 法的大门，各自刷完了一遍LeetCode的题目，这其中碰到了很多困难，当然也少不了用了Google以及参考 了别人的代码。 做完一遍下来，陡然发现，很多题目还是忘记了，再次碰到又不知道如何下手，其实这就是典型的没有理 解，掌握透。所以我们决定，应该好好的将自己做题的思路记录下来，一个知识点，自己能弄懂，写出来 让大家都明白，同时能做到举一反三，触类旁通，那么在一定程度上面才算是真的掌握了。 于是就有了现在准备开始的这本书：《LeetCode题解》，用来记录我们刷LeetCode题目时候的心酸历史。 我们保证，书中的代码一定通过了当时LeetCode的测试，虽然后续可能因为LeetCode测试条件的改变导致 某些解题无法通过，但我们会实时的跟进。 编程语言使用C++，代码风格上面并没有强制的采用什么编码规范，毕竟是算法解题，只需要代码清晰易 懂就可以了。 我们准备按照LeetCode的题型分类来组织章节，譬如Array，Hash Table等，而对每个章节里面的题目，通 常采用由易到难的方式进行说明。采用这种方式，能让我们在短时间内快速学习掌握某一类知识，同时也 便于讲解说明。 当然，除了LeetCode现有的题目，我们也希望在每个章节加入相关的扩展知识，这需要我们参考大量现有 的算法书籍，鉴于个人精力时间有限，可能并不会完全实施。 最后，我们非常欢迎大家的反馈（前提是有人看我们的东西）。如果你有任何的意见建议，欢迎在Github 的issue里面提出，或者直接与我们联系。Thanks Contributor陈心宇
张晓 MaintainerSiddonTang Introduction4 LeetCode题解ArrayArray5 LeetCode题解Remove ElementGiven an array and a value, remove all instances of that & value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length. 作为开胃菜，我当然选取了最容易的一道题目，在一个数组里面移除指定value，并且返回新的数组长度。 这题唯一需要注意的地方在于 in place ，不能新建另一个数组。 方法很简单，使用两个游标i，j，遍历数组，如果碰到了value，使用j记录位置，同时递增i，直到下一个非 value出现，将此时i对应的值复制到j的位置上，增加j，重复上述过程直到遍历结束。这时候j就是新的数组 长度。 代码如下：class Solution { public:
int removeElement(int A[], int n, int elem) {
int i = 0;
int j = 0;
for(i = 0; i & n; i++) {
if(A[i] == elem) {
A[j] = A[i];
} };举一个最简单的例子，譬如数组为1，2，2，3，2，4，我们需要删除2，首先初始化i和j为0，指向第一个 位置，因为第一个元素为1，所以A[0] = A[0]，i和j都加1，而第二个元素为2，我们递增i，直到碰到3，此时 A[1] = A[3]，也就是3，递增i和j，这时候下一个元素又是2，递增i，直到碰到4，此时A[2] = A[5]，也就是 4，再次递增i和j，这时候数组已经遍历完毕，结束。这时候j的值为3，刚好就是新的数组的长度。Remove Element6 LeetCode题解Remove Duplicates from Sorted ArrayGiven a sorted array, remove the duplicates in place such that & each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2]. 这道题目与前一题Remove Element比较类似。但是在一个排序好的数组里面删除重复的元素。 首先我们需要知道，对于一个排好序的数组来说， A[N + 1] &= A[N] ，我们仍然使用两个游标i和j来处 理，假设现在i = j + 1，如果A[i] == A[j]，那么我们递增i，直到A[i] != A[j]，这时候我们再设置A[j + 1] = A[i]，同时递增i和j，重复上述过程直到遍历结束。 代码如下：class Solution { public:
int removeDuplicates(int A[], int n) {
if(n == 0) {
int j = 0;
for(int i = 1; i & n; i++) {
if(A[j] != A[i]) {
A[++j] = A[i];
return j + 1;
} };譬如一个数组为1，1，2，3，首先i = 1，j = 0，这时候A[i] = A[j]，于是递增i，碰到2，不等于1，此时设置 A[j + 1] = A[i]，也就是A[1] = A[2]，递增i和j为3和1，这时候A[3] != A[1]，设置A[j + 1] = A[i]，也就是A[2] = A[3]，再次递增，遍历结束。这时候新的数组长度就为2 + 1，也就是3。Remove Duplicates from Sorted Array IIFollow up for &Remove Duplicates&: What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3]. 紧接着上一题，同样是移除重复的元素，但是可以允许最多两次重复元素存在。 Remove Duplicates from Sorted Array 7 LeetCode题解仍然是第一题的思路，但是我们需要用一个计数器来记录重复的次数，如果重复次数大于等于2，我们会按 照第一题的方式处理，如果不是重复元素了，我们将计数器清零。 代码如下：class Solution { public:
int removeDuplicates(int A[], int n) {
if(n == 0) {
int j = 0;
int num = 0;
for(int i = 1; i & n; i++) {
if(A[j] == A[i]) {
if(num & 2) {
A[++j] = A[i];
A[++j] = A[i];
return j + 1;
} };Remove Duplicates from Sorted Array8 LeetCode题解Plus OneGiven a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. 这道题目很简单，就是考的加法进位问题。直接上代码：class Solution { public:
vector&int& plusOne(vector&int& &digits) {
vector&int& res(digits.size(), 0);
int sum = 0;
int one = 1;
for(int i =
digits.size() - 1; i &= 0; i--) {
sum = one + digits[i];
one = sum / 10;
res[i] = sum % 10;
if(one & 0) {
res.insert(res.begin(), one);
} };Plus One9 LeetCode题解Pascal's TriangleGiven numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return[
[1,3,3,1],
[1,4,6,4,1] ]要得到一个帕斯卡三角，我们只需要找到规律即可。 第k层有k个元素 每层第一个以及最后一个元素值为1 对于第k（k & 2）层第n（n & 1 && n & k）个元素A[k][n]，A[k][n] = A[k-1][n-1] + A[k-1][n] 知道了上面的规律，就很好做了，我们使用一个二维数组来存储整个三角，代码如下：class Solution { public:
vector&vector&int& & generate(int numRows) {
vector&vector&int& &
vals.resize(numRows);
for(int i = 0; i & numR i++) {
vals[i].resize(i + 1);
vals[i][0] = 1;
vals[i][vals[i].size() - 1] = 1;
for(int j = 1; j & vals[i].size() - 1; j++) {
vals[i][j] = vals[i - 1][j - 1] + vals[i - 1][j];
} };Pascal's Triangle IIGiven an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1]. 不同于上一题，这里我们仅仅需要得到的第k层的集合，但只能使用O(k)的空间。所以不能用前面二维数组 的方式，只能使用一位数组滚动计算。 Pascal's Triangle 10 LeetCode题解在第一题里面，我们知道，帕斯卡三角的计算公式是这样的，A[k][n] = A[k-1][n-1] + A[k-1][n]。 假设现在数组存放的第3层的数据，[1, 3, 3, 1]，如果我们需要计算第4层的数据，如果我们从前往后计算， 譬如A[4][2]= A[3][1] + A[3][2]，也就是4，但是因为只有一个数组，所以需要将4这个值覆盖到2这个位置， 那么我们计算A[4][3]的时候就会出现问题了，因为这时候A[3][2]不是3，而是4了。 为了解决这个问题，我们只能从后往前计算，仍然是上面那个例子，我们实现计算A[4][3] = A[3][2] + A[3] [3]，也就是6，我们将6直接覆盖到3这个位置，但不会影响我们计算A[4][2]，因为A[4][2] = A[3][1] + A[3] [2]，已经不会涉及到3这个位置了。 理解了如何计算，代码就很简单了：class Solution { public:
vector&int& getRow(int rowIndex) {
vector&int&
vals.resize(rowIndex + 1, 1);
for(int i = 0; i & rowIndex + 1; ++i) {
for(int j = i - 1; j &= 1; --j) {
vals[j] = vals[j] + vals[j - 1];
} };Pascal's Triangle11 LeetCode题解Merge Sorted ArrayGiven two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. A和B都已经是排好序的数组，我们只需要从后往前比较就可以了。 因为A有足够的空间容纳A + B，我们使用游标i指向m + n - 1，也就是最大数值存放的地方，从后往前遍历 A，B，谁大就放到i这里，同时递减i。 代码如下：class Solution { public:
void merge(int A[], int m, int B[], int n) {
int i = m + n - 1;
int j = m - 1;
int k = n - 1;
while(i &= 0) {
if(j &= 0 && k &= 0) {
if(A[j] & B[k]) {
A[i] = A[j];
A[i] = B[k];
} else if(j &= 0) {
A[i] = A[j];
} else if(k &= 0) {
A[i] = B[k];
} };Merge Sorted Array12 LeetCode题解2SumGiven an array of intergers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2 Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 题目翻译： 这道题目的意思是给定一个数组和一个值，让求出这个数组中两个值的和等于这个给定值的坐 标。输出是有要求的，1， 坐标较小的放在前面，较大的放在后面。2， 这俩坐标不能为零。 题目分析： 第一步： 我们要分析题意，其中有三个关键点： 1.
求出来的坐标值要按序排列。 2.
这两个坐标不能从零开始。 3.
这道题目假设是只有一组答案符合要求，这样降低了我们解题的难度。 根据题目我们可以得到以下信息： 1.
我们得到坐标的时候，要根据大小的顺序放入数组。 2.
因为坐标值不能为零，所以我们得到的坐标都要+1。 3.
因为有且只有一组答案符合要求，所以这大大的降低了这道题目的难度，也就是说，我们只要找到符 合条件的两个数，存入结果，直接终止程序，返回答案即可。 解题思路： 这道题不是很难，是leetcode最开始的题目，要求很明确，很直接，如果我们用两个for循环， O(n2)的时间复杂度去求解的话，很容易计算出来，但这明显不是面试官需要的答案。brute force只有在你 不知道如何优化题目的时候，将就的给出的一个解法。。那么我们能不能用O(n)的时间复杂度去解这道题 呢？很显然是可以的，不过，天下没有掉馅饼的事情啦，既然优化了时间复杂度，我们就要牺牲空间复杂 度啦。在这里用什么呢？stack？queue？vector？还是hash_map? 对于stack和queue，除了pop外，查找的时间复杂度也是O(n)。明显不是我们所需要的，那么什么数据结构 的查找时间复杂度小呢？很显然是 hash_map, 查找的时间复杂度理想情况下是O(1)。所以我们先来考虑 hash_map，看看hash_map怎么求解这个问题。 我们可以先把这个数组的所有元素存到hashmap中，一次循环就行， 时间复杂度为O(n),之后对所给数组在 进行遍历，针对其中的元素我们只要用another_number = target-numbers[i],之后用hashmap的find function来查找这个值，如果存在的话，在进行后续比较（详见代码），如果不存在的话，继续查找，好 啦，思路已经摆在这里了，详见代码吧。class Solution { public:
vector&int& twoSum(vector&int& &numbers, int target) {
//边角问题，我们要考虑边角问题的处理
vector&int& Sum13 LeetCode题解
if(numbers.size() &= 1)
//新建一个map&key,value& 模式的来存储numbers里面的元素和index，
//这里的unordered_map相当于hash_map
unordered_map&int,int& myM
for(int i = 0; i & numbers.size(); ++i)
myMap[numbers[i]] = i;
for(int i = 0; i & numbers.size(); ++i)
int rest_val = target - numbers[i];
if(myMap.find(rest_val)!=myMap.end())
int index = myMap[rest_val];
if(index == i)
//如果是同一个数字，我们就pass，是不会取这个值的
if(index & i)
ret.push_back(index+1);
//这里+1是因为题目说明白了要non-zero based index
ret.push_back(i+1);
ret.push_back(i+1);
ret.push_back(index+1);
} };以上解法的要注意的是记得要检查这两个坐标是不是相同的，因为我们并不需要同样的数字。3SumGiven an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. 题目翻译： 给定一个整型数组num，找出这个数组中满足这个条件的所有数字： num[i]+num[j]+num[k] = 0. 并且所有 的答案是要和其他不同的，也就是说两个相同的答案是不被接受的。 题目的两点要求： 1.
每个答案组里面的三个数字是要从大到小排列起来的。 2.
每个答案不可以和其他的答案相同。 题目分析： Sum 14 LeetCode题解1.
每一个答案数组triplet中的元素是要求升序排列的。 2.
不能包含重复的答案数组。 解题思路： 1.
根据第一点要求： 因为要求每个答案数组中的元素是升序排列的，所以在开头我们要对数组进行排 序。 2.
根据第二点要求： 因为不能包含重复的答案数组，所以我们要在代码里面做一切去掉重复的操作，对 于数组，这样的操作是相同的。最开始我做leetcode的时候是把所有满足条件的答案数组存起来，之后 再用map进行处理，感觉那样太麻烦了，所以这次给出的答案是不需要额外空间的。 时间复杂度分析： 对于这道题，因为是要找三个元素，所以怎样都要O(n2)的时间复杂度，目前我没有想出来O(n)时间复杂度 的解法。 归根结底，其实这是two pointers的想法，定位其中两个指针，根据和的大小来移动另外一个。解题中所要 注意的就是一些细节问题。好了，上代码吧。class Solution { public: //constant space version
vector&vector&int& & threeSum(vector&int& &num) {
vector&vector&int&&
//corner case invalid check
if(num.size() &= 2)
//first we need to sort the array because we need the non-descending order
sort(num.begin(), num.end());
for(int i = 0; i & num.size()-2; ++i)
int j = i+1;
int k = num.size()-1;
while(j & k)
vector&int&
//create a tmp vector to store each triplet which satisfy the sol
if(num[i]+num[j]+num[k] == 0)
curr.push_back(num[i]);
curr.push_back(num[j]);
curr.push_back(num[k]);
ret.push_back(curr);
//this two while loop is used to skip the duplication solution
while(j & k&&num[j-1] == num[j])
while(j & k&&num[k] == num[k+1])
else if(num[i]+num[j]+num[k] & 0)
//if the sum is less than the target value, we neeSum15 LeetCode题解
//this while loop also is used to skip the duplication solution
while(i & num.size()-1&&num[i] == num[i+1])
} };根据以上代码，我们要注意的就是用于去除重复的那三个while loop。一些细节问题比如for loop中的i & num.size()-2;因为j和k都在i后面，所以减掉两位。当然如果写成i& num.size(); 也是可以通过测试的，但感 觉思路不是很清晰。另外一点，就是不要忘记了corner case check呀。3Sum ClosestGiven an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You man assume that each input would have exactly one solution. 题目翻译： 给定一个整形数组S和一个具体的值，要求找出在这数组中三个元素的和和这个给定的值最小。input只有 一个有效答案。 题目要求： 这道题比较直接，也没有什么具体的要求。 题目分析： 1.
最短距离：两个整数的最短距离是0.这点对于这道题比较重要，别忽略。 2.
这道题和3Sum几乎同出一辙，所以方便于解题，我们还是在开头要对数组进行排序，要么没法定位指 针移动。 3.
另外，这道题中用到了INT_MAX这个值，这个值和 INT_MIN是相对应的，在很多比较求最大值最小值 的情况，经常用这两个变量。 解题思路： 这道题的解题方法和3Sum几乎相同，设定三个指针，固定两个，根据和的大小移动另外一个。属于这道题 目自己的东西就是distance比较这块儿，建立一个tmp distance和min distance比较。 时间复杂度分析： 这道题目和3Sum几乎是一个思路，所以时间复杂度为O(n2)。 代码如下： Sum 16 LeetCode题解class Solution { public:
int threeSumClosest(vector&int& &num, int target) {
//invalid corner case check
if(num.size() &= 2)
return -1;
int ret = 0;
//first we suspect the distance between the sum and the target is the largest number in int
int distance = INT_MAX;
sort(num.begin(),num.end());
//sort is needed
for(int i = 0; i & num.size()-2; ++i)
int j = i+1;
int k = num.size()-1;
while(j & k)
int tmp_val = num[i]+num[j]+num[k];
if(tmp_val & target)
tmp_distance = target - tmp_
if(tmp_distance & distance)
distance = tmp_
ret = num[i]+num[j]+num[k];
else if(tmp_val & target)
tmp_distance = tmp_val-
if(tmp_distance & distance)
distance = tmp_
ret= num[i]+num[j]+num[k];
else //note: in this case, the sum is 0, 0 means the shortest distance from the sum t
ret = num[i]+num[j]+num[k];
} };总结： 这道题的解决方法主要要注意以下几点： 1.
首先要对数组进行排序。 2.
0是两个数组间最小的距离。 Sum 17 LeetCode题解4SumGiven an array S of n integers, are there elements a, b, c and d in S such that a+b+c+d = target? Find all unique quadruplets in the array which gives the sume of target. Note: 1.
Elements in quadruplets (a, b, c, d) must be in non-descending order. (ie, a&=b&=c&=d) 2.
The solution must not contain duplicates quadruplets. 题目翻译： 给定一个整型数字数组num和一个目标值target，求出数组中所有的组合满足条件： num[a]+num[b]+num[c]+num[d] = target. 并且要满足的条件是： 1.
num[a] &= num[b] &= num[c] &= num[d] 2.
答案中的组合没有重复的. 题目分析： 这道题和3Sum几乎同出一辙，只不过是要求四个数字的和，在时间复杂度上要比3Sum高一个数量级。对 于两点要求的处理： 1.
首先要对整个数组进行排序，这样得到的答案自然是排序好的. 2.
对于重复答案的处理和3Sum是一摸一样的。 解题思路： 同3Sum. 时间复杂度分析： 这道题的解法，我选择的是空间复杂度为1， 时间复杂度为O(n3).对于这样的问题，如果到了KSum(K&=5), 我觉得可以用hash_map来牺牲空间复杂度换取好一些的时间复杂度. 代码如下：class Solution { public:
vector&vector&int& & fourSum(vector&int& &num, int target) {
vector&vector&int&&
if(num.size() &= 3) //invalid corner case check
sort(num.begin(), num.end()); //cause we need the result in quadruplets should be non-descend
for(int i = 0; i & num.size()-3; ++i)
if(i & 0 && num[i] == num[i-1])
for(int j = i+1; j & num.size()-2; ++j)
if(j & i+1 && num[j] == num[j-1])
Sum18 LeetCode题解
int k = j+1;
int l = num.size()-1;
while(k & l)
int sum = num[i]+num[j]+num[k]+num[l];
if(sum == target)
vector&int&
//create a temporary vector to store the each quadruplets
curr.push_back(num[i]);
curr.push_back(num[j]);
curr.push_back(num[k]);
curr.push_back(num[l]);
ret.push_back(curr);
//the two while loops are used to skip the duplication solutions
while(k&l && num[k] == num[k-1]);
while(k&l && num[l] == num[l+1]);
else if(sum & target)
//we can do this operation because of we sort the array at the beginnin
} };根据上述代码，我觉得要说明白的一点是: 1.
我用do{}while来代替了while进行重复答案的处理，为什么要这样呢？是因为如果换成了while， leetcode的test sample过不去，报的错误是超出了时间的限制，我认为如果要用while，应该是多进行 了++k 还有--l的操作吧。换成了do{}while就可以通过所有的test case.问题扩展 KSum根据以上的2Sum, 3Sum, 3Sum Cloest， 还有4Sum，我相信只要认真看完每道题的解法的童鞋，都 会发现一定的规律，相信这时候会有人想，如果变成KSum问题，我们应该如何求解？这是个很好的 想法，下面，我们来看看问题扩展. 首先，对于2Sum，我们用的解法是以空间复杂度来换取时间复杂度，那么，2Sum我们可不可以in place来 解？时间复杂度又是多少？ 答案是当然可以，我们可以先sort一遍，之后再扫一变，sort的时间复杂度是 O(nlogn)，扫一遍是O(n),因此，这种解法的时间复杂度是O(nlogn), 当然，如果对于要找index，leetcode上 的题不能用这个方法，因为我们sort一遍之后，index会发生一些变化。但是我们可以用以下这个function来 作为一个Helper function对于K Sum(考虑到如果K & 2, sort一遍数组的时间开销不算是主要的时间开销了):Sum19 LeetCode题解void twoSum(vector&int& &numbers, int begin, int first, int second, int target, vector&vector
if(begin &= numbers.size()-1)
int e = numbers.size()-1;
while(b & e)
int rest = numbers[b]+numbers[e];
if(rest == target)
vector&int& tmp_
tmp_ret.push_back(first);
tmp_ret.push_back(second);
tmp_ret.push_back(numbers[b]);
tmp_ret.push_back(numbers[e]);
ret.push_back(tmp_ret);
while(b&e && numbers[b] == numbers[b-1]);
while(b&e && numbers[e] == numbers[e+1]);
else if(rest & target)
}给个例子，对于4Sum，我们可以调用这个function，代码如下:class Solution { public:
void twoSum(vector&int& &numbers, int begin, int first, int second, int target, vector
if(begin &= numbers.size()-1)
int e = numbers.size()-1;
while(b & e)
int rest = numbers[b]+numbers[e];
if(rest == target)
vector&int& tmp_
tmp_ret.push_back(first);
tmp_ret.push_back(second);
tmp_ret.push_back(numbers[b]);
tmp_ret.push_back(numbers[e]);
ret.push_back(tmp_ret);
while(b&e && numbers[b] == numbers[b-1]);
while(b&e && numbers[e] == numbers[e+1]);
else if(rest & target)Sum20 LeetCode题解
vector&vector&int& & fourSum(vector&int& &num, int target) {
vector&vector&int&&
if(num.size() &= 3) //invalid corner case check
sort(num.begin(), num.end()); //cause we need the result in quadruplets should be non-descend
for(int i = 0; i & num.size()-3; ++i)
if(i & 0 && num[i] == num[i-1])
for(int j = i+1; j & num.size()-2; ++j)
if(j & i+1 && num[j] == num[j-1])
twoSum(num, j+1, num[i], num[j], target-(num[i]+num[j]), ret);
} };以上解法可以延伸到KSum.不过是相当于对于n-2个数做嵌套循环。这么写出来使得思路清晰，以后遇到了 类似问题可以解决。Sum21 LeetCode题解Find Minimum in Rotated Sorted ArraySuppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. You may assume no duplicate exists in the array. 这题要求在一个轮转了的排序数组里面找到最小值，我们可以用二分法来做。 首先我们需要知道，对于一个区间A，如果A[start] & A[stop]，那么该区间一定是有序的了。 假设在一个轮转的排序数组A，我们首先获取中间元素的值，A[mid]，mid = (start + stop) / 2。因为数组没 有重复元素，那么就有两种情况： A[mid] & A[start]，那么最小值一定在右半区间，譬如[4,5,6,7,0,1,2]，中间元素为7，7 & 4，最小元素 一定在[7,0,1,2]这边，于是我们继续在这个区间查找。 A[mid] & A[start]，那么最小值一定在左半区间，譬如[7,0,1,2,4,5,6]，这件元素为2，2 & 7，我们继续 在[7,0,1,2]这个区间查找。 代码如下:class Solution { public:
int findMin(vector&int& &num) {
int size = num.size();
if(size == 0) {
} else if(size == 1) {
return num[0];
} else if(size == 2) {
return min(num[0], num[1]);
int start = 0;
int stop = size - 1;
while(start & stop - 1) {
if(num[start] & num[stop]) {
return num[start];
int mid = start + (stop - start) / 2;
if(num[mid] & num[start]) {
} else if(num[mid] & num[start]) {
}Find Minimum in Rotated Sorted Array22 LeetCode题解
return min(num[start], num[stop]);
} };Find Minimum in Rotated Sorted ArraySuppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. The array may contain duplicates. 这题跟上题唯一的区别在于元素可能有重复，我们仍然采用上面的方法，只是需要处理mid与start相等这种 额外情况。 A[mid] & A[start]，右半区间查找。 A[mid] & A[start]，左半区间查找。 A[mid] = A[start]，出现这种情况，我们跳过start，重新查找，譬如[2,2,2,1]，A[mid] = A[start]都为2， 这时候我们跳过start，使用[2,2,1]继续查找。 代码如下:class Solution { public:
int findMin(vector&int& &num) {
int size = num.size();
if(size == 0) {
} else if(size == 1) {
return num[0];
} else if(size == 2) {
return min(num[0], num[1]);
int start = 0;
int stop = size - 1;
while(start & stop - 1) {
if(num[start] & num[stop]) {
return num[start];
int mid = start + (stop - start) / 2;
if(num[mid] & num[start]) {
} else if(num[mid] & num[start]) {
start++;Find Minimum in Rotated Sorted Array23 LeetCode题解
return min(num[start], num[stop]);
} };这题需要注意，如果重复元素很多，那么最终会退化到遍历整个数组，而不是二分查找了。Find Minimum in Rotated Sorted Array24 LeetCode题解Largest Rectangle in HistogramGiven n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area = 10 unit. For example, Given height = [2,1,5,6,2,3], return 10. 这道题目算是比较难得一道题目了，首先最简单的做法就是对于任意一个bar，向左向右遍历，直到高度小 于该bar，这时候计算该区域的矩形区域面积。对于每一个bar，我们都做如上处理，最后就可以得到最大 值了。当然这种做法是O(n2)，铁定过不了大数据集合测试的。 从上面我们直到，对于任意一个bar n，我们得到的包含该bar n的矩形区域里面bar n是最小的。我们使用ln 和rn来表示bar n向左以及向右第一个小于bar n的bar的索引位置。 譬如题目中的bar 2的高度为5，它的ln为1，rn为4。包含bar 2的矩形区域面积为(4 - 1 - 1) * 5 = 10。 我们可以从左到右遍历所有bar，并将其push到一个stack中，如果当前bar的高度小于栈顶bar，我们pop出 栈顶的bar，同时以该bar计算矩形面积。那么我们如何知道该bar的ln和rn呢？rn铁定就是当前遍历到的bar 的索引，而ln则是当前的栈顶bar的索引，因为此时栈顶bar的高度一定小于pop出来的bar的高度。 为了更好的处理最后一个bar的情况，我们在实际中会插入一个高度为0的bar，这样就能pop出最后一个bar 并计算了。Largest Rectangle in Histogram25 LeetCode题解代码如下：class Solution { public:
int largestRectangleArea(vector&int& &height) {
vector&int& s;
//插入高度为0的bar
height.push_back(0);
int sum = 0;
int i = 0;
while(i & height.size()) {
if(s.empty() || height[i] & height[s.back()]) {
s.push_back(i);
int t = s.back();
s.pop_back();
//这里还需要考虑stack为空的情况
sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
} };Largest Rectangle in Histogram26 LeetCode题解Maximal RectangleGiven a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 这题是一道难度很大的题目，至少我刚开始的时候完全不知道怎么做，也是google了才知道的。 这题要求在一个矩阵里面求出全部包含1的最大矩形面积，譬如这个：
0 1 0 0我们可以知道，最大的矩形面积为6。也就是下图中虚线包围的区域。那么我们如何得到这个区域呢？
|--------|
|--------|
0对于上面哪一题，我们先去掉最下面的一行，然后就可以发现，它可以转化成一个直方图，数据为[2, 2, 2, 0]，我们认为1就是高度，如果碰到0，譬如上面最右列，则高度为0，而计算这个直方图最大矩形面积就很 容易了，我们已经在Largest Rectangle in Histogram处理了。 所以我们可以首先得到每一行的直方图，分别求出改直方图的最大区域，最后就能得到结果了。 代码如下：class Solution { public:
int maximalRectangle(vector&vector&char& & &matrix) {
if(matrix.empty() || matrix[0].empty()) {
int m = matrix.size();
int n = matrix[0].size();
vector&vector&int& & height(m, vector&int&(n, 0));
for(int i = 0; i & m; i++) {
for(int j = 0; j & n; j++) {
if(matrix[i][j] == '0') {
height[i][j] = 0;
height[i][j] = (i == 0) ? 1 : height[i - 1][j] + 1;
}Maximal Rectangle27 LeetCode题解
int maxArea = 0;
for(int i = 0; i & m; i++) {
maxArea = max(maxArea, largestRectangleArea(height[i]));
return maxA
int largestRectangleArea(vector&int& &height) {
vector&int& s;
height.push_back(0);
int sum = 0;
int i = 0;
while(i & height.size()) {
if(s.empty() || height[i] & height[s.back()]) {
s.push_back(i);
int t = s.back();
s.pop_back();
sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
} };Maximal Rectangle28 LeetCode题解Palindrome NumberDetermine whether an integer is a palindrome. Do this without extra space. 题目翻译: 给定一个数字，要求判断这个数字是否为回文数字. 比如121就是回文数字，122就不是回文数字. 解题思路: 这道题很明显是一道数学题,计算一个数字是否是回文数字，我们其实就是将这个数字除以10， 保留他的余数，下次将余数乘以10，加上这个数字再除以10的余数. 需要注意的点: 1.
负数不是回文数字. 2.
0是回文数字. 时间复杂度: logN 代码如下:class Solution { public:
bool isPalindrome(int x) {
else if(x == 0)
int tmp = x;
int y = 0;
while(x != 0)
y = y*10 + x%10;
if(y == tmp)
} };Palindrome Number29 LeetCode题解Search a 2D MatrixWrite an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example, Consider the following matrix:[
[10, 11, 16, 20],
[23, 30, 34, 50] ]题目翻译: 给定一个矩阵和一个特定值，要求写出一个高效的算法在这个矩阵中快速的找出是否这个给定的 值存在. 但是这个矩阵有以下特征. 1.
对于每一行，数值是从左到右从小到大排列的. 2.
对于每一列，数值是从上到下从小到大排列的. 题目解析: 对于这个给定的矩阵，我们如果用brute force解法，用两个嵌套循环，O(n2)便可以得到答案.但 是我们需要注意的是这道题已经给定了这个矩阵的两个特性，这两个特性对于提高我们算法的时间复杂度 有很大帮助，首先我们给出一个O(n)的解法，也就是说我们可以固定住右上角的元素，根据递增或者递减 的规律，我们可以判断这个给定的数值是否存在于这个矩阵当中.class Solution { public:
bool searchMatrix(vector&vector&int& & &matrix, int target) {
/* we set the corner case as below:
1, if the row number of input matrix is 0, we set it false
2, if the colomun number of input matrix is 0, we set it false*/
if(matrix.size() == 0)
if(matrix[0].size() == 0)
int rowNumber = 0;
int colNumber = matrix[0].size()-1;
while(rowNumber & matrix.size() && colNumber &= 0)
if(target & matrix[rowNumber][colNumber])
else if(target & matrix[rowNumber][colNumber])
}Search a 2D Matrix30 LeetCode题解};Search a 2D Matrix31 LeetCode题解Search for a RangeGiven a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 这题要求在一个排好序可能有重复元素的数组里面找到包含某个值的区间范围。要求使用O(log n)的时间， 所以我们采用两次二分查找。首先二分找到第一个该值出现的位置，譬如m，然后在[m, n)区间内第二次二 分找到最后一个该值出现的位置。代码如下：class Solution { public:
vector&int& searchRange(int A[], int n, int target) {
if(n == 0) {
return vector&int&({-1, -1});
vector&int& v;
int low = 0;
int high = n - 1;
//第一次二分找第一个位置
while(low &= high) {
int mid = low + (high - low) / 2;
if(A[mid] &= target) {
high = mid - 1;
low = mid + 1;
if(low & n && A[low] == target) {
v.push_back(low);
return vector&int&({-1, -1});
high = n - 1;
//从第一个位置开始进行第二次二分，找最后一个位置
while(low &= high) {
int mid = low + (high - low) / 2;
if(A[mid] &= target) {
low = mid + 1;
high = mid - 1;
}Search for a Range32 LeetCode题解
v.push_back(high);
} };Search for a Range33 LeetCode题解Search Insert PositionGiven a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 这题要求在一个排好序的数组查找某值value，如果存在则返回对应index，不存在则返回能插入到数组中的 index（保证数组有序）。 对于不存在的情况，我们只需要在数组里面找到最小的一个值大于value的index，这个index就是我们可以 插入的位置。譬如[1, 3, 5, 6]，查找2，我们知道3是最小的一个大于2的数值，而3的index为1，所以我们需 要在1这个位置插入2。如果数组里面没有值大于value，则插入到数组末尾。 我们采用二分法解决：class Solution { public:
int searchInsert(int A[], int n, int target) {
int low = 0;
int high = n - 1;
while(low &= high) {
int mid = low + (high - low) / 2;
if(A[mid] == target) {
} else if(A[mid] & target) {
low = mid + 1;
high = mid - 1;
} };Search Insert Position34 LeetCode题解Find Peak ElementA peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2. 这题要求我们在一个无序的数组里面找到一个peak元素，所谓peak，就是值比两边邻居大就行了。 对于这题，最简单地解法就是遍历数组，只要找到第一个元素，大于两边就可以了，复杂度为O(N)。但这 题还可以通过二分来做。 首先我们找到中间节点mid，如果大于两边返回当前index就可以了，如果左边的节点比mid大，那么我们可 以继续在左半区间查找，这里面一定存在一个peak，为什么这么说呢？假设此时的区间范围为[0, mid 1]， 因为num[mid - 1]一定大于num[mid]了，如果num[mid - 2] &= num[mid - 1]，那么num[mid - 1]就是一 个peak。如果num[mid - 2] & num[mid - 1]，那么我们就继续在[0, mid - 2]区间查找，因为num[-1]为负无 穷，所以最终我们绝对能在左半区间找到一个peak。同理右半区间一样。 代码如下：class Solution { public:
int findPeakElement(const vector&int& &num) {
int n = num.size();
if(n == 1) {
int start = 0;
int end = n - 1;
int mid = 0;
while(start &= end) {
mid = start + (end - start) / 2;
if((mid == 0 || num[mid] &= num[mid - 1]) &&
(mid == n - 1 || num[mid] &= num[mid + 1])) {
}else if(mid & 0 && num[mid-1] & num[mid]) {
end = mid - 1;
start = mid + 1;
} };Find Peak Element35 LeetCode题解Find Peak Element36 LeetCode题解Bit ManipulationBit Manipulation37 LeetCode题解Missing NumberGiven an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums =
2 . Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? 题目翻译: 从0到n之间取出n个不同的数，找出漏掉的那个。 注意：你的算法应当具有线性的时间复杂度。 你能实现只占用常数额外空间复杂度的算法吗？ 题目分析: 最直观的思路是对数据进行排序，然后依次扫描，便能找出漏掉的数字，但是基于比较的排序算 法的时间复杂度至少是 nlog(n) ，不满足题目要求。 一种可行的具有线性时间复杂度的算法是求和。对0到n求和，然后对给出的数组求和，二者之差即为漏掉 的数字。但是这种方法不适用于0是漏掉的数字的情况，因为此时两个和是相同的。（或者也能由此得出漏 掉的数字是0） 从CPU指令所耗费的时钟周期来看，比加法更高效率的运算是异或(XOR)运算。本题的标签里有位运算， 暗示本题可以用位运算的方法解决。 异或运算的一个重要性质是，相同的数异或得0，不同的数异或不为0，且此性质可以推广到多个数异或的 情形。本题的解法如下，首先将0到n这些数进行异或运算，然后对输入的数组进行异或运算，最后将两个 结果进行异或运算，结果便是漏掉的数字，因为其他数字在两个数组中都是成对出现的，异或运算会得到 0。 时间复杂度：O(n) 空间复杂度：O(1) 代码如下:class Solution { public:
int missingNumber(vector&int&& nums) {
int x = 0;
for (int i = 0; i &= nums.size(); i++) x ^= i;
for (auto n : nums) x ^= n;
} };Missing Number38 LeetCode题解Power of TwoGiven an integer, write a function to determine if it is a power of two. 题目翻译: 给出一个整数，判断它是否是2的幂。 题目分析: 2的整数次幂对应的二进制数只含有0个或者1个1，所以我们要做的就是判断输入的数的二进制表 达形式里是否符合这一条件。 有一种corner case需要注意，当输入的数为负数的时候，一定不是2的幂。 时间复杂度：O(n) 空间复杂度：O(1) 代码如下:class Solution { public:
bool isPowerOfTwo(int n) {
if (n & 0) return
bool hasOne =
while (n & 0) {
if (n & 1) {
if (hasOne) {
return hasO
} };Power of Two39 LeetCode题解Number of 1 BitsWrite a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight). For example, the 32-bit integer
has binary representation
, so the function should return 3.题目翻译: 给出一个整数，求它包含二进制1的位数。例如，32位整数 11 的二进制表达形式 是
，那么函数应该返回3。 题目分析: 设输入的数为n，把n与1做二进制的与(AND)运算，即可判断它的最低位是否为1。如果是的话， 把计数变量加一。然后把n向右移动一位，重复上述操作。当n变为0时，终止算法，输出结果。 时间复杂度：O(n) 空间复杂度：O(1) 代码如下:class Solution { public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n & 0) {
count += n & 1;
} };Number of 1 Bits40 LeetCode题解Tree树是一种重要的非线性数据结构，广泛地应用于计算机技术的各个领域。采用树可以实现一些高效地查找 算法，例如数据库系统中用到的红黑树等。 树本身的定义是递归的，因此很多涉及到树的算法通常都可以用递归的方式来实现。然而递归算法在数据 量较大的时候效率很低，所以通常会将递归改写成迭代算法。 涉及到树的题目主要包括树的遍历，平衡二叉树，查找二叉树等。Tree41 LeetCode题解Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 这题要求我们求出一个二叉树最大深度，也就是从根节点到最远的叶子节点的距离。 对于这题，我们只需要递归遍历二叉树，达到一个叶子节点的时候，记录深度，我们就能得到最深的深度 了。 代码如下：class Solution { public:
int maxDepth(TreeNode *root) {
if(!root) {
//首先初始化num为最小值
num = numeric_limits&int&::min();
travel(root, 1);
void travel(TreeNode* node, int level) {
//如果没有左子树以及右子树了，就到了叶子节点
if(!node-&left && !node-&right) {
num = max(num, level);
if(node-&left) {
travel(node-&left, level + 1);
if(node-&right) {
travel(node-&right, level + 1);
} };Minimum Depth of Binary TreeGiven a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Depth of Binary Tree 42 LeetCode题解这题跟上题几乎一样，区别在于需要求出根节点到最近的叶子节点的深度，我们仍然使用遍历的方式。 代码如下：class Solution { public:
int minDepth(TreeNode *root) {
if(!root) {
//初始化成最大值
n = numeric_limits&int&::max();
int d = 1;
depth(root, d);
void depth(TreeNode* node, int& d) {
//叶子节点，比较
if(!node-&left && !node-&right) {
n = min(n, d);
if(node-&left) {
depth(node-&left, d);
if(node-&right) {
depth(node-&right, d);
} };Depth of Binary Tree43 LeetCode题解Construct Binary Tree from Inorder and Postorder TraversalGiven inorder and postorder traversal of a tree, construct the binary tree. 要知道如何构建二叉树，首先我们需要知道二叉树的几种遍历方式，譬如有如下的二叉树：
--------|------
7前序遍历 1245367 中序遍历 4251637 后续遍历 4526731 具体到上面这一题，我们知道了一个二叉树的中序遍历以及后序遍历的结果，那么如何构建这颗二叉树 呢？ 仍然以上面那棵二叉树为例，我们可以发现，对于后序遍历来说，最后一个元素一定是根节点，也就是1。 然后我们在中序遍历的结果里面找到1所在的位置，那么它的左半部分就是其左子树，有半部分就是其右子 树。 我们将中序遍历左半部分425取出，同时发现后序遍历的结果也在相应的位置上面，只是顺序稍微不一样， 也就是452。我们可以发现，后序遍历中的2就是该子树的根节点。 上面说到了左子树，对于右子树，我们取出637，同时发现后序遍历中对应的数据偏移了一格，并且顺序也 不一样，为673。而3就是这颗右子树的根节点。 重复上述过程，通过后续遍历找到根节点，然后在中序遍历数据中根据根节点拆分成两个部分，同时将对 应的后序遍历的数据也拆分成两个部分，重复递归，就可以得到整个二叉树了。 代码如下：class Solution { public:
unordered_map&int, int& m;
TreeNode *buildTree(vector&int& &inorder, vector&int& &postorder) {
if(postorder.empty()) {
return NULL;
for(int i = 0; i & inorder.size(); i++) {
m[inorder[i]] = i;
return build(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);Construct Binary Tree44 LeetCode题解
TreeNode* build(vector&int&& inorder, int s0, int e0,
vector&int&& postorder, int s1, int e1) {
if(s0 & e0 || s1 & e1) {
return NULL;
TreeNode* root = new TreeNode(postorder[e1]);
int mid = m[postorder[e1]];
int num = mid - s0;
root-&left = build(inorder, s0, mid - 1, postorder, s1, s1 + num - 1);
root-&right = build(inorder, mid + 1, e0, postorder, s1 + num, e1 - 1);
} };这里我们需要注意，为了保证快速的在中序遍历结果里面找到根节点，我们使用了hash map。Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. 这题跟上面那题类似，通过前序遍历和中序遍历的结果构造二叉树，我们只需要知道前序遍历的第一个值 就是根节点，那么仍然可以采用上面提到的方式处理： 通过前序遍历找到根节点 通过根节点将中序遍历数据拆分成两部分 对于各个部分重复上述操作 代码如下：class Solution { public:
unordered_map&int, int& m;
TreeNode *buildTree(vector&int& &preorder, vector&int& &inorder) {
if(preorder.empty()) {
return NULL;
for(int i = 0; i & inorder.size(); i++) {
m[inorder[i]] = i;
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
TreeNode* build(vector&int&& preorder, int s0, int e0, vector&int& &inorder, int s1,
if(s0 & e0 || s1 & e1) {Construct Binary Tree45 LeetCode题解
return NULL;
int mid = m[preorder[s0]];
TreeNode* root = new TreeNode(preorder[s0]);
int num = mid - s1;
root-&left = build(preorder, s0 + 1, s0 + num, inorder, s1, mid - 1);
root-&right = build(preorder, s0 + num + 1, e0, inorder, mid + 1, e1);
} };可以看到，这两道题目，只要能清楚了树的几种遍历方式，以及找到如何找到根节点，并通过中序遍历拆 分成两个子树，就能很容易的搞定了，唯一需要注意的是写代码的时候拆分索引位置要弄对。Construct Binary Tree46 LeetCode题解Binary Tree Level Order TraversalGiven a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},
7return its level order traversal as:[
[15,7] ]题目翻译: 给定一颗二叉树，返回一个二维数组，使这个二维数组的每一个元素代表着二叉树的一层的元 素.例子已经明确给出. 题目分析: 对于二叉树的问题，我们第一想到的就是DFS或者BFS, DFS更易于理解代码，如果处理数据量 不是很大的话.对于这样的面试题，我建议用DFS来求解. 需要注意的点为: 1.
对于一棵树，如果我们要求每一层的节点，并且存在一个二维数组里，首先我们要建一个二维数组， 但是这个二维数组建多大的合适呢？我们就要求出这颗树的深度，根据深度来建立二维数组. 2.
题目要求为从左往右添加,所以我们也就是要先放左边的节点，再放右边的节点. 3.
对于这道题，我们首先就是要用DFS来求出这颗树的高度，之后再用DFS对于每一层遍历，这样节省 了空间复杂度. 时间复杂度分析: 由于两次DFS是并列的，并没有嵌套，所以我们的时间复杂度为O(n). 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/Binary Tree Level Order Traversal47 LeetCode题解class Solution { public: /* for this question, we need to construct the ret vector first
thus, we need to know the depth of this tree, we write a simple
function to calculate the height of this tree */
vector&vector&int& & levelOrder(TreeNode *root) {
int depth = getHeight(root);
vector&vector&int&& ret(depth);
if(depth == 0) //invalid check
getSolution(ret,root,0);
void getSolution(vector&vector&int&&& ret, TreeNode* root, int level)
if(root == NULL)
ret[level].push_back(root-&val);
getSolution(ret,root-&left,level+1);
getSolution(ret,root-&right,level+1);
int getHeight(TreeNode* root)
if(root == NULL)
int left = getHeight(root-&left);
int right = getHeight(root-&right);
int height = (left & right?left:right)+1;
} };Binary Tree Level Order Traversal IIGiven a binary tree, return the bottom-up level order traversal of its nodes' values. (from left to right, level by level from leaf to root) For example: Given binary tree {3,9,20,#,#,15,7},
7return its level order traversal as:[
[3]Binary Tree Level Order Traversal48 LeetCode题解]题目翻译: 给定一颗二叉树， 返回一个二维数组，这个二维数组要满足这个条件，二维数组的第一个一维 数组要是这可二叉树的最下面一层，之后以此类推，根据以上例子应该知道要求的条件。 题目分析 && 解题思路: 这道题和Binary Tree Level Order Traversal 几乎是一摸一样的，唯一不同的就是二 维数组的存储顺序，详见以下代码. 时间复杂度: O(n)-树的dfs均为O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
vector&vector&int& & levelOrderBottom(TreeNode *root) {
int depth = height(root);
vector&vector&int&& ret(depth);
if(depth == 0)
DFS(ret,ret.size()-1, root);
void DFS(vector&vector&int&&& ret, int level, TreeNode* root)
if(root == NULL)
ret[level].push_back(root-&val);
DFS(ret,level-1,root-&left);
DFS(ret,level-1,root-&right);
/* get the height first of all */
int height(TreeNode* root)
if(root == NULL)
int left_side = height(root-&left);
int right_side = height(root-&right);
int height = (left_side & right_side?left_side:right_side)+1;
} };Binary Tree Level Order Traversal49 LeetCode题解Binary Tree Zigzag Level Order TraversalGiven a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20,#,#,15,7},
7return its zigzag level order traversal as:[
[15,7] ]如果完成了上面两题，这题应该是很简单的，我们只需要将得到的数据按照zigzag的方式翻转一下，代码 如下：class Solution { public: vector&vector&int& &
vector&vector&int& & zigzagLevelOrder(TreeNode *root) {
build(root, 1);
for(int i = 1; i & vals.size(); i+=2) {
reverse(vals[i].begin(), vals[i].end());
void build(TreeNode* node, int level) {
if(!node) {
if(vals.size() &= level - 1) {
vals.push_back(vector&int&());
vals[level - 1].push_back(node-&val);
if(node-&left) {
build(node-&left, level + 1);
}Binary Tree Level Order Traversal50 LeetCode题解
if(node-&right) {
build(node-&right, level + 1);
} };Binary Tree Level Order Traversal51 LeetCode题解Symmetric TreeGiven a binary tree, check whether it is a mirror of itself(ie, symmetric around its center) For example, this tree is symmetric:
3But the following tree is not.
3题目翻译： 判断一棵树是不是自己的镜像， 根据以上正反两个例子，我想大家都明白这道题的题目要求 了，简单明了. 解题思路: 递归: 这道题没什么特别的地方，现在这里简单的分析一下解题思路，从根节点往下，我们要判 断三个条件. 1.
左右两个节点的大小是否相同. 2.
左节点的左孩子是否和右节点的右孩子相同. 3.
左节点的右孩子是否和右节点的左孩子相同. 循环: 这道题的难点在于循环解法， 如果是循环解法，我们必须要用到额外的存储空间用于回溯，关键是 对于这道题目， 我们要用多少？要怎么用？要用什么样的存储空间？ 递归求解，如果以上三个条件对于每一层都满足，我们就可以认为这棵树是镜像树. 时间复杂度: 递归:本质其实就是DFS,时间复杂度为O(n),空间复杂度O(1) 递归:时间复杂度O(n),空间复杂度 O(n) 递归代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };Symmetric Tree52 LeetCode题解 */ class Solution { public:
bool isSymmetric(TreeNode *root) {
if(root == NULL)
return Helper(root-&left,root-&right);
bool Helper(TreeNode* left, TreeNode* right)
if(left == NULL&&right == NULL)
else if(left == NULL||right == NULL)
bool cond1 = left-&val == right-&
bool cond2 = Helper(left-&left,right-&right);
bool cond3 = Helper(left-&right, right-&left);
return cond1&&cond2&&cond3;
} };循环解法: 我们主要想介绍一下这道题的循环解法，对于循环，我们要满足对于每一层进行check，代替了 递归，一般树的循环遍历，我们都是用FIFO的queue来作为临时空间存储变量的，所以这道题我们也选取 了queue，但是我们用两个queue，因为我们要对于左右同时进行检查，很显然一个queue是不够的，具体 实现细节，咱们还是看代码吧，，我相信代码更能解释方法. 循环代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool isSymmetric(TreeNode *root) {
if(root == NULL)
TreeNode* n1 = root-&
TreeNode* n2 = root-&
if(!n1&&!n2)
if((!n1&&n2)||(n1&&!n2))
queue&TreeNode*& Q1;
queue&TreeNode*& Q2;
Q1.push(n1);
Q2.push(n2);
while(!Q1.empty() && !Q2.empty())Symmetric Tree53 LeetCode题解
TreeNode* tmp1 = Q1.front();
TreeNode* tmp2 = Q2.front();
if((!tmp1&&tmp2) || (tmp1&&!tmp2))
if(tmp1&&tmp2)
if(tmp1-&val != tmp2-&val)
Q1.push(tmp1-&left);
Q1.push(tmp1-&right); //note: this line we should put the mirror sequence in two queu
Q2.push(tmp2-&right);
Q2.push(tmp2-&left);
} };Symmetric Tree54 LeetCode题解Same TreeGiven two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same values. 题目翻译: 给两棵树，写一个函数来判断这两棵树是否相同. 我们判定一棵树是否相同的条件为这两棵树的 结构相同，并且每个节点的值相同. 解题思路: 这道题中规中矩，很简单，我们直接用DFS前序遍历这两棵树就可以了. 时间复杂度分析: 因为是DFS, 所以时间复杂度为O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(p == NULL && q == NULL)
else if(p == NULL || q == NULL)
if(p-&val == q-&val)
bool left = isSameTree(p-&left, q-&left);
bool right = isSameTree(p-&right,q-&right);
return left&&
} };Same Tree55 LeetCode题解Balanced Binary TreeGiven a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 题目翻译: 给定一颗二叉树， 写一个函数来检测这棵树是否是平衡二叉树. 对于这个问题, 一颗平衡树的定 义是其中任意节点的左右子树的高度差不大于1. 解题思路: 这道题其实就是应用DFS，对于一颗二叉树边计算树的高度边计算差值，针对树里面的每一个节 点计算它的左右子树的高度差，如果差值大于1，那么就返回-1，如果不大于1，从下往上再次检测. 时间复杂度: 由于是运用DFS，所以时间复杂度为O(n). 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool isBalanced(TreeNode *root) {
//corner case check
if(root == NULL)
int isBalanced = getHeight(root);
if(isBalanced != -1)
int getHeight(TreeNode* root)
if(root == NULL)
int leftHeight = getHeight(root-&left);
if(leftHeight == -1)
return -1;
int rightHeight = getHeight(root-&right);
if(rightHeight == -1)
return -1;
int diffHeight = rightHeight & leftHeight? rightHeight-leftHeight:leftHeight-rightH
if(diffHeight & 1)
return -1;Balanced Binary Tree56 LeetCode题解
return diffHeight = (rightHeight&leftHeight?rightHeight:leftHeight)+1;
} };Balanced Binary Tree57 LeetCode题解Path SumGiven a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the below binary tree and sum = 22,
1return true, as there exist a root-to-leaf path 5-&4-&11-&2 which sum is 22. 题目翻译: 给定一颗二叉树和一个特定值，写一个方法来判定这棵树是否存在这样一种条件，使得从root到 其中一个叶子节点的路径的和等于给定的sum值. 解题思路: 这道题很常规，直接用DFS就可以求解. 时间复杂度: O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool hasPathSum(TreeNode *root, int sum) {
if(root == NULL)
return DFS(sum, 0, root);
bool DFS(int target, int sum, TreeNode* root)
if(root == NULL)
sum += root-&
if(root-&left == NULL && root-&right == NULL)
if(sum == target)
return Path Sum58 LeetCode题解
bool leftPart = DFS(target, sum, root-&left);
bool rightPart = DFS(target, sum, root-&right);
return leftPart||rightP
} };Path Sum59 LeetCode题解Binary Tree Depth Order Traversal前面我们解决了tree的level order遍历问题，这里我们需要来处理tree的depth order，也就是前序，中序和 后序遍历。Binary Tree Preorder TraversalGiven a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},
3return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? 给定一颗二叉树，使用迭代的方式进行前序遍历。 因为不能递归，所以我们只能使用stack来保存迭代状态。 对于前序遍历，根节点是最先访问的，然后是左子树，最后才是右子树。当访问到根节点的时候，我们需 要将右子树压栈，这样访问左子树之后，才能正确地找到对应的右子树。 代码如下：class Solution { public:
vector&int& preorderTraversal(TreeNode *root) {
vector&int&
if(root == NULL) {
vector&TreeNode*&
//首先将root压栈
nodes.push_back(root);
while(!nodes.empty()) {
TreeNode* n = nodes.back();
vals.push_back(n-&val);
//访问了该节点，出栈
nodes.pop_back();Binary Tree Depth Order Traversal60 LeetCode题解
//如果有右子树，压栈保存
if(n-&right) {
nodes.push_back(n-&right);
//如果有左子树，压栈保存
if(n-&left) {
nodes.push_back(n-&left);
} };Binary Tree Inorder Traversal给定一颗二叉树，使用迭代的方式进行中序遍历。 对于中序遍历，首先遍历左子树，然后是根节点，最后才是右子树，所以我们需要用stack记录每次遍历的 根节点，当左子树遍历完成之后，从stack弹出根节点，得到其右子树，开始新的遍历。 代码如下：class Solution { public:
vector&int& inorderTraversal(TreeNode *root) {
vector&int&
if(root == NULL) {
vector&TreeNode*&
TreeNode* p =
while(p || !nodes.empty()) {
//这里一直遍历左子树，将根节点压栈
while(p) {
nodes.push_back(p);
if(!nodes.empty()) {
p = nodes.back();
vals.push_back(p-&val);
//将根节点弹出，获取右子树
nodes.pop_back();
} };Binary Tree Depth Order Traversal61 LeetCode题解Binary Tree Postorder Traversal给定一颗二叉树，使用迭代的方式进行后序遍历。 对于后序遍历，首先遍历左子树，然后是右子树，最后才是根节点。当遍历到一个节点的时候，首先我们 将右子树压栈，然后将左子树压栈。这里需要注意一下出栈的规则，对于叶子节点来说，直接可以出栈， 但是对于根节点来说，我们需要一个变量记录上一次出栈的节点，如果上一次出栈的节点是该根节点的左 子树或者右子树，那么该根节点可以出栈，否则这个根节点是新访问的节点，将右和左子树分别压栈。 代码如下：class Solution { public:
vector&int& postorderTraversal(TreeNode *root) {
vector&int&
if(root == NULL) {
vector&TreeNode*&
TreeNode* pre = NULL;
nodes.push_back(root);
while(!nodes.empty()) {
TreeNode* p = nodes.back();
//如果不判断pre，我们就没法正确地出栈了
if((p-&left == NULL && p-&right == NULL) ||
(pre != NULL && (pre == p-&left || pre == p-&right))) {
vals.push_back(p-&val);
nodes.pop_back();
//右子树压栈
if(p-&right != NULL) {
nodes.push_back(p-&right);
//左子树压栈
if(p-&left != NULL) {
nodes.push_back(p-&left);
} };总结可以看到，树的遍历通过递归或者堆栈的方式都是比较容易的，网上还有更牛的不用栈的方法，只是我没 理解，就不做过多说明了。 Binary Tree Depth Order Traversal 62 LeetCode题解Binary Tree Depth Order Traversal63 LeetCode题解Populating Next Right Pointers in Each NodeGiven a binary tree
struct TreeLinkNode {
TreeLinkNode *
TreeLinkNode *
TreeLinkNode *
}Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree,
7After calling your function, the tree should look like:
2 -& 3 -& NULL
4-&5-&6-&7 -& NULL这题需要在一棵完全二叉树中使用next指针连接旁边的节点，我们可以发现一些规律。 如果一个子节点是根节点的左子树，那么它的next就是该根节点的右子树，譬如上面例子中的4，它的 next就是2的右子树5。 如果一个子节点是根节点的右子树，那么它的next就是该根节点next节点的左子树。譬如上面的5，它 的next就是2的next（也就是3）的左子树。 所以代码如下：class Solution { public:Populating Next Right Pointers in Each Node64 LeetCode题解
void connect(TreeLinkNode *root) {
if(!root) {
TreeLinkNode* p =
TreeLinkNode* first = NULL;
while(p) {
//记录下层第一个左子树
if(!first) {
first = p-&
//如果有左子树，那么next就是父节点
if(p-&left) {
p-&left-&next = p-&
//叶子节点了，遍历结束
//如果有next，那么设置右子树的next
if(p-&next) {
p-&right-&next = p-&next-&
//转到下一层
first = NULL;
} };Populating Next Right Pointers in Each Node IIWhat if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary tree,
7After calling your function, the tree should look like:
2 -& 3 -& NULLPopulating Next Right Pointers in Each Node65 LeetCode题解
4-& 5 -& 7 -& NULL不同于上一题，这题的二叉树并不是完全二叉树，我们不光需要提供first指针用来表示一层的第一个元素， 同时也需要使用另一个lst指针表示该层上一次遍历的元素。那么我们只需要处理好如何设置last的next指针 就可以了。 代码如下:class Solution { public:
void connect(TreeLinkNode *root) {
if(!root) {
TreeLinkNode* p =
TreeLinkNode* first = NULL;
TreeLinkNode* last = NULL;
while(p) {
//设置下层第一个元素
if(!first) {
if(p-&left) {
first = p-&
} else if(p-&right) {
first = p-&
if(p-&left) {
//如果有last，则设置last的next
if(last) {
last-&next = p-&
//last为left
last = p-&
if(p-&right) {
//如果有last，则设置last的next
if(last) {
last-&next = p-&
//last为right
last = p-&
//如果有next，则转到next
if(p-&next) {
//转到下一层
last = NULL;
first = NULL;Populating Next Right Pointers in Each Node66 LeetCode题解
} };其实我们可以看到，第一题只是第二题的特例，所以第二题的解法也同样适用于第一题。Populating Next Right Pointers in Each Node67 LeetCode题解Convert Sorted List to Binary Search TreeGiven a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 这题需要将一个排好序的链表转成一个平衡二叉树，我们知道，对于一个二叉树来说，左子树一定小于根 节点，而右子树大于根节点。所以我们需要找到链表的中间节点，这个就是根节点，链表的左半部分就是 左子树，而右半部分则是右子树，我们继续递归处理相应的左右部分，就能够构造出对应的二叉树了。 这题的难点在于如何找到链表的中间节点，我们可以通过fast，slow指针来解决，fast每次走两步，slow每 次走一步，fast走到结尾，那么slow就是中间节点了。 代码如下：class Solution { public:
TreeNode *sortedListToBST(ListNode *head) {
return build(head, NULL);
TreeNode* build(ListNode* start, ListNode* end) {
if(start == end) {
return NULL;
ListNode* fast =
ListNode* slow =
while(fast != end && fast-&next != end) {
slow = slow-&
fast = fast-&next-&
TreeNode* node = new TreeNode(slow-&val);
node-&left = build(start, slow);
node-&right = build(slow-&next, end);
} };Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST. 这题类似上面那题，同样地解题方式，对于数组来说，能更方便的得到中间节点，代码如下：class Solution { public:Convert Sorted List/Array to Binary Search Tree68 LeetCode题解
TreeNode *sortedArrayToBST(vector&int& &num) {
return build(num, 0, num.size());
TreeNode* build(vector&int&& num, int start, int end) {
if(start &= end) {
return NULL;
int mid = start + (end - start) / 2;
TreeNode* node = new TreeNode(num[mid]);
node-&left = build(num, start, mid);
node-&right = build(num, mid + 1, end);
} };Convert Sorted List/Array to Binary Search Tree69 LeetCode题解Path Sum IIGiven a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22.
[5,4,11,2],
[5,8,4,5] ]题目翻译： 给定一个二叉树，并且给定一个值，找出所有从根节点到叶子节点和等于这个给定值的路径.上 面的例子可以很好地让读者理解这个题目的目的. 解题思路: 这个题目和Path Sum的解法几乎是一模一样，都是用dfs来进行求解，不过就是在传参数的时候 有些不同了，因为题目的要求也不同. 时间复杂度: O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
vector&vector&int& & pathSum(TreeNode *root, int sum) {
vector&vector&int&&
if(root == NULL)
vector&int&
DFS(ret,curr,sum,0,root);Path Sum II70 LeetCode题解
void DFS(vector&vector&int&&& ret, vector&int& curr, int sum, int tmpsum, TreeNode* root)
if(root == NULL)
tmpsum+=root-&
curr.push_back(root-&val);
if(tmpsum == sum)
if(root-&left == NULL&&root-&right == NULL)
ret.push_back(curr);
DFS(ret,curr,sum,tmpsum,root-&left);
DFS(ret,curr,sum,tmpsum,root-&right);
} };Path Sum II71 LeetCode题解Flatten Binary Tree to Linked ListGiven a binary tree, flatten it to a linked list in-place. For example, Given
6The flattened tree should look like:
6给定一颗二叉树，将其扁平化处理，我们可以看到处理之后的节点顺序其实跟前序遍历原二叉树的一致， 所以我们只需要前序遍历二叉树同时处理就可以了。代码如下：class Solution { public:
void flatten(TreeNode *root) {
if(!root) {
TreeNode dummy(0);
TreeNode* n = &
ns.push_back(root);
while(!ns.empty()) {
TreeNode* p = ns.back();
ns.pop_back();
//挂载到右子树
n-&right = p;
n = p;Flatten Binary Tree to Linked List72 LeetCode题解
//右子树压栈
if(p-&right) {
ns.push_back(p-&right);
p-&right = NULL;
//左子树压栈
if(p-&left) {
ns.push_back(p-&left);
p-&left = NULL;
} };Flatten Binary Tree to Linked List73 LeetCode题解Validate Binary Search TreeGiven a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. 这题需要判断是不是一个正确的二叉搜索树，比较简单地一道题。 我们通过递归整棵树来解决，代码如下：class Solution { public:
bool isValidBST(TreeNode *root) {
return valid(root, numeric_limits&int&::min(), numeric_limits&int&::max());
bool valid(TreeNode* node, int minVal, int maxVal) {
if(!node) {
if(node-&val &= minVal || node-&val &= maxVal) {
return valid(node-&left, minVal, node-&val) &&
valid(node-&right, node-&val, maxVal);
} };Validate Binary Search Tree74 LeetCode题解Recover Binary Search TreeTwo elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? 这题需要修复一颗二叉搜索树的两个交换节点数据，我们知道对于一颗二叉搜索树来说，如果按照中序遍 历，那么它输出的值是递增有序的，所以我们只需要按照中序遍历输出，在输出结果里面找到两个异常数 据（比它后面输出结果大），交换这两个节点的数据就可以了。 但是这题要求使用O(1)的空间，如果采用通常的中序遍历（递归或者栈）的方式，都需要O(N)的空间，所 以这里我们用Morris Traversal的方式来进行树的中序遍历。 Morris Traversal中序遍历的原理比较简单： 如果当前节点的左孩子为空，则输出当前节点并将其有孩子作为当前节点。 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点，也就 是当前节点左子树的最右边的那个节点。 如果前驱节点的右孩子为空，则将它的右孩子设置为当前节点，当前节点更新为其左孩子。 如果前驱节点的右孩子为当前节点，则将前驱节点的右孩子设为空，输出当前节点，当前节点更 新为其右孩子。 重复上述过程，直到当前节点为空，递归的时候我们同时需要记录错误的节点。那么我们如何知道一个节 点的数据是不是有问题呢？对于中序遍历来说，假设当前节点为cur，它的前驱节点为pre，如果cur的值小 于pre的值，那么cur和pre里面的数据就是交换的了。 代码如下：class Solution { public:
void recoverTree(TreeNode *root) {
TreeNode* cur = 0;
TreeNode* pre = 0;
TreeNode* p1 = 0;
TreeNode* p2 = 0;
TreeNode* preCur = 0;
bool found =
if(!root) {
while(cur) {
if(!cur-&left) {Recover Binary Search Tree75 LeetCode题解
//记录p1和p2
if(preCur && preCur-&val & cur-&val) {
if(!found) {
cur = cur-&
pre = cur-&
while(pre-&right && pre-&right != cur) {
pre = pre-&
if(!pre-&right) {
pre-&right =
cur = cur-&
//记录p1和p2
if(preCur-&val & cur-&val) {
if(!found) {
pre-&right = NULL;
cur = cur-&
if(p1 && p2) {
int t = p1-&
p1-&val = p2-&
p2-&val = t;
} };Recover Binary Search Tree76 LeetCode题解Binary Tree PathGiven a binary tree, return all root-to-leaf paths. For example, given the following binary tree:
5All root-to-leaf paths are:[&1-&2-&5&, &1-&3&]题目翻译： 给定一棵二叉树，返回所有从根节点到叶节点的路径。 题目分析： 本题属于二叉树的遍历问题，可以用深度优先搜索来解决。 使用栈来记录遍历过程中访问过的节点。递归地访问每个节点的子节点，如果遇到叶节点，则输出记录的 路径。返回上一层之前弹出栈顶元素。 C++的vector容器也能做到后进先出，所以下面的代码并没有使用 std::stack类来实现。 生成输出的字符串时，可以使用std::stringstream类来完成，类似于Java和C#中的StringBuilder。/**
* Definition for a binary tree node.
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
vector&string& binaryTreePaths(TreeNode* root) {
vector&string&
if (root == nullptr) return
vector&int&
bfs(root, path, result);
} private:
// 递归函数，深度优先搜索
void bfs(TreeNode* node, vector&int&& path, vector&string&& result) {
if (node == nullptr)
path.push_back(node-&val);Binary Tree Path77 LeetCode题解
if (node-&left == nullptr && node-&right == nullptr)
result.push_back(generatePath(path));
if (node-&left != nullptr) {
bfs(node-&left, path, result);
path.pop_back();
if (node-&right != nullptr) {
bfs(node-&right, path, result);
path.pop_back();
// 辅助函数，用于生成路径字符串
string generatePath(vector&int& path) {
stringstream
for (i = 0; i & path.size() - 1; i++) ss && path[i] && &-&&;
ss && path[i];
return ss.str();
} };Binary Tree Path78 LeetCode题解Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path
which represents the number
123 . Find the total sum of all root-to-leaf numbers. For example,
3The root-to-leaf path
represents the number
12 . The root-to-leaf path
represents the number
13 . Return the sum = 12 + 13 = 25. 题目翻译： 给定一棵二叉树，仅包含0到9这些数字，每一条从根节点到叶节点的路径表示一个数。例如， 路径 1-&2-&3 表示数值123。求出所有路径表示的数值的和。 上述例子中，路径 1-&2 表示数值12，路 径 1-&3 表示数值13。它们的和是25。 题目分析: 从根节点到叶节点的遍历方法是深度优先搜索(DFS)。解决本题只需在遍历过程中记录路径中的 数字，在到达叶节点的时候把记录下来的数字转换成数值，加到和里面即可。 时间复杂度: O(n) 代码如下:/**
* Definition for a binary tree node.
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
int sumNumbers(TreeNode* root) {
vector&int&
int sum = 0;
dfs(root, arr, sum);
int vec2num(vector&int&& vec) {
int num = 0;
for (auto n : vec) {
num = num * 10 + n;
}Sum Root to Leaf Numbers79 LeetCode题解
void dfs(TreeNode* node, vector&int&& arr, int& sum) {
if (node == nullptr)
arr.push_back(node-&val);
if (node-&left == nullptr && node-&right == nullptr) {
sum += vec2num(arr);
if (node-&left != nullptr) dfs(node-&left, arr, sum);
if (node-&right != nullptr) dfs(node-&right, arr, sum);
arr.pop_back();
} };Sum Root to Leaf Numbers80 LeetCode题解Dynamic ProgrammingDynamic Programming81 LeetCode题解Best Time to Buy and Sell StockSay you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.}
leetcode-solution
LeetCode题解Table of Contents1.
Introduction 2.
Remove Element ii.
Remove Duplicates from Sorted Array iii.
Plus One iv.
Pascal's Triangle v.
Merge Sorted Array vi.
Find Minimum in Rotated Sorted Array viii.
Largest Rectangle in Histogram ix.
Maximal Rectangle x.
Palindrome Number xi.
Search a 2D Matrix xii.
Search for a Range xiii.
Search Insert Position xiv.
Find Peak Element 3.
Bit Manipulation i.
Missing Number ii.
Power of Two iii.
Number of 1 Bits 4.
Depth of Binary Tree ii.
Construct Binary Tree iii.
Binary Tree Level Order Traversal iv.
Symmetric Tree v.
Same Tree vi.
Balanced Binary Tree vii.
Path Sum viii.
Binary Tree Depth Order Traversal ix.
Populating Next Right Pointers in Each Node x.
Convert Sorted List/Array to Binary Search Tree xi.
Path Sum II xii.
Flatten Binary Tree to Linked List xiii.
Validate Binary Search Tree xiv.
Recover Binary Search Tree xv.
Binary Tree Path xvi.
Sum Root to Leaf Numbers 5.
Dynamic Programming i.
Best Time To Buy And Sell Stock ii.
Unique Paths iii.
Maximum Subarray iv.
Climbing Stairs 2 LeetCode题解v.
Triangle vi.
Unique Binary Search Trees vii.
Perfect Squares 6.
Backtracking i.
Combination ii.
Subsets iii.
Permutation 7.
Jump Game ii.
Gas Station iii.
Word Break 8.
Linked List i.
Linked List Cycle ii.
Remove Duplicates from Sorted List iii.
Merge Sorted Lists iv.
Reverse Linked List v.
Swap Nodes in Pairs vi.
Sort List vii.
Rotate List viii.
Reorder List ix.
Partition List x.
Add Two Numbers xi.
Copy List with Random Pointer 9.
Reverse Integer 10.
Add Binary ii.
Basic Calculator II3 LeetCode题解前言首先声明，我和张晓都不是算法牛人，确切的说应该是算法的门外汉，小白一个。所以我们为了撬开算 法的大门，各自刷完了一遍LeetCode的题目，这其中碰到了很多困难，当然也少不了用了Google以及参考 了别人的代码。 做完一遍下来，陡然发现，很多题目还是忘记了，再次碰到又不知道如何下手，其实这就是典型的没有理 解，掌握透。所以我们决定，应该好好的将自己做题的思路记录下来，一个知识点，自己能弄懂，写出来 让大家都明白，同时能做到举一反三，触类旁通，那么在一定程度上面才算是真的掌握了。 于是就有了现在准备开始的这本书：《LeetCode题解》，用来记录我们刷LeetCode题目时候的心酸历史。 我们保证，书中的代码一定通过了当时LeetCode的测试，虽然后续可能因为LeetCode测试条件的改变导致 某些解题无法通过，但我们会实时的跟进。 编程语言使用C++，代码风格上面并没有强制的采用什么编码规范，毕竟是算法解题，只需要代码清晰易 懂就可以了。 我们准备按照LeetCode的题型分类来组织章节，譬如Array，Hash Table等，而对每个章节里面的题目，通 常采用由易到难的方式进行说明。采用这种方式，能让我们在短时间内快速学习掌握某一类知识，同时也 便于讲解说明。 当然，除了LeetCode现有的题目，我们也希望在每个章节加入相关的扩展知识，这需要我们参考大量现有 的算法书籍，鉴于个人精力时间有限，可能并不会完全实施。 最后，我们非常欢迎大家的反馈（前提是有人看我们的东西）。如果你有任何的意见建议，欢迎在Github 的issue里面提出，或者直接与我们联系。Thanks Contributor陈心宇
张晓 MaintainerSiddonTang Introduction4 LeetCode题解ArrayArray5 LeetCode题解Remove ElementGiven an array and a value, remove all instances of that & value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length. 作为开胃菜，我当然选取了最容易的一道题目，在一个数组里面移除指定value，并且返回新的数组长度。 这题唯一需要注意的地方在于 in place ，不能新建另一个数组。 方法很简单，使用两个游标i，j，遍历数组，如果碰到了value，使用j记录位置，同时递增i，直到下一个非 value出现，将此时i对应的值复制到j的位置上，增加j，重复上述过程直到遍历结束。这时候j就是新的数组 长度。 代码如下：class Solution { public:
int removeElement(int A[], int n, int elem) {
int i = 0;
int j = 0;
for(i = 0; i & n; i++) {
if(A[i] == elem) {
A[j] = A[i];
} };举一个最简单的例子，譬如数组为1，2，2，3，2，4，我们需要删除2，首先初始化i和j为0，指向第一个 位置，因为第一个元素为1，所以A[0] = A[0]，i和j都加1，而第二个元素为2，我们递增i，直到碰到3，此时 A[1] = A[3]，也就是3，递增i和j，这时候下一个元素又是2，递增i，直到碰到4，此时A[2] = A[5]，也就是 4，再次递增i和j，这时候数组已经遍历完毕，结束。这时候j的值为3，刚好就是新的数组的长度。Remove Element6 LeetCode题解Remove Duplicates from Sorted ArrayGiven a sorted array, remove the duplicates in place such that & each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2]. 这道题目与前一题Remove Element比较类似。但是在一个排序好的数组里面删除重复的元素。 首先我们需要知道，对于一个排好序的数组来说， A[N + 1] &= A[N] ，我们仍然使用两个游标i和j来处 理，假设现在i = j + 1，如果A[i] == A[j]，那么我们递增i，直到A[i] != A[j]，这时候我们再设置A[j + 1] = A[i]，同时递增i和j，重复上述过程直到遍历结束。 代码如下：class Solution { public:
int removeDuplicates(int A[], int n) {
if(n == 0) {
int j = 0;
for(int i = 1; i & n; i++) {
if(A[j] != A[i]) {
A[++j] = A[i];
return j + 1;
} };譬如一个数组为1，1，2，3，首先i = 1，j = 0，这时候A[i] = A[j]，于是递增i，碰到2，不等于1，此时设置 A[j + 1] = A[i]，也就是A[1] = A[2]，递增i和j为3和1，这时候A[3] != A[1]，设置A[j + 1] = A[i]，也就是A[2] = A[3]，再次递增，遍历结束。这时候新的数组长度就为2 + 1，也就是3。Remove Duplicates from Sorted Array IIFollow up for &Remove Duplicates&: What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3]. 紧接着上一题，同样是移除重复的元素，但是可以允许最多两次重复元素存在。 Remove Duplicates from Sorted Array 7 LeetCode题解仍然是第一题的思路，但是我们需要用一个计数器来记录重复的次数，如果重复次数大于等于2，我们会按 照第一题的方式处理，如果不是重复元素了，我们将计数器清零。 代码如下：class Solution { public:
int removeDuplicates(int A[], int n) {
if(n == 0) {
int j = 0;
int num = 0;
for(int i = 1; i & n; i++) {
if(A[j] == A[i]) {
if(num & 2) {
A[++j] = A[i];
A[++j] = A[i];
return j + 1;
} };Remove Duplicates from Sorted Array8 LeetCode题解Plus OneGiven a non-negative number represented as an array of digits, plus one to the number. The digits are stored such that the most significant digit is at the head of the list. 这道题目很简单，就是考的加法进位问题。直接上代码：class Solution { public:
vector&int& plusOne(vector&int& &digits) {
vector&int& res(digits.size(), 0);
int sum = 0;
int one = 1;
for(int i =
digits.size() - 1; i &= 0; i--) {
sum = one + digits[i];
one = sum / 10;
res[i] = sum % 10;
if(one & 0) {
res.insert(res.begin(), one);
} };Plus One9 LeetCode题解Pascal's TriangleGiven numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return[
[1,3,3,1],
[1,4,6,4,1] ]要得到一个帕斯卡三角，我们只需要找到规律即可。 第k层有k个元素 每层第一个以及最后一个元素值为1 对于第k（k & 2）层第n（n & 1 && n & k）个元素A[k][n]，A[k][n] = A[k-1][n-1] + A[k-1][n] 知道了上面的规律，就很好做了，我们使用一个二维数组来存储整个三角，代码如下：class Solution { public:
vector&vector&int& & generate(int numRows) {
vector&vector&int& &
vals.resize(numRows);
for(int i = 0; i & numR i++) {
vals[i].resize(i + 1);
vals[i][0] = 1;
vals[i][vals[i].size() - 1] = 1;
for(int j = 1; j & vals[i].size() - 1; j++) {
vals[i][j] = vals[i - 1][j - 1] + vals[i - 1][j];
} };Pascal's Triangle IIGiven an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1]. 不同于上一题，这里我们仅仅需要得到的第k层的集合，但只能使用O(k)的空间。所以不能用前面二维数组 的方式，只能使用一位数组滚动计算。 Pascal's Triangle 10 LeetCode题解在第一题里面，我们知道，帕斯卡三角的计算公式是这样的，A[k][n] = A[k-1][n-1] + A[k-1][n]。 假设现在数组存放的第3层的数据，[1, 3, 3, 1]，如果我们需要计算第4层的数据，如果我们从前往后计算， 譬如A[4][2]= A[3][1] + A[3][2]，也就是4，但是因为只有一个数组，所以需要将4这个值覆盖到2这个位置， 那么我们计算A[4][3]的时候就会出现问题了，因为这时候A[3][2]不是3，而是4了。 为了解决这个问题，我们只能从后往前计算，仍然是上面那个例子，我们实现计算A[4][3] = A[3][2] + A[3] [3]，也就是6，我们将6直接覆盖到3这个位置，但不会影响我们计算A[4][2]，因为A[4][2] = A[3][1] + A[3] [2]，已经不会涉及到3这个位置了。 理解了如何计算，代码就很简单了：class Solution { public:
vector&int& getRow(int rowIndex) {
vector&int&
vals.resize(rowIndex + 1, 1);
for(int i = 0; i & rowIndex + 1; ++i) {
for(int j = i - 1; j &= 1; --j) {
vals[j] = vals[j] + vals[j - 1];
} };Pascal's Triangle11 LeetCode题解Merge Sorted ArrayGiven two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. A和B都已经是排好序的数组，我们只需要从后往前比较就可以了。 因为A有足够的空间容纳A + B，我们使用游标i指向m + n - 1，也就是最大数值存放的地方，从后往前遍历 A，B，谁大就放到i这里，同时递减i。 代码如下：class Solution { public:
void merge(int A[], int m, int B[], int n) {
int i = m + n - 1;
int j = m - 1;
int k = n - 1;
while(i &= 0) {
if(j &= 0 && k &= 0) {
if(A[j] & B[k]) {
A[i] = A[j];
A[i] = B[k];
} else if(j &= 0) {
A[i] = A[j];
} else if(k &= 0) {
A[i] = B[k];
} };Merge Sorted Array12 LeetCode题解2SumGiven an array of intergers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2 Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 题目翻译： 这道题目的意思是给定一个数组和一个值，让求出这个数组中两个值的和等于这个给定值的坐 标。输出是有要求的，1， 坐标较小的放在前面，较大的放在后面。2， 这俩坐标不能为零。 题目分析： 第一步： 我们要分析题意，其中有三个关键点： 1.
求出来的坐标值要按序排列。 2.
这两个坐标不能从零开始。 3.
这道题目假设是只有一组答案符合要求，这样降低了我们解题的难度。 根据题目我们可以得到以下信息： 1.
我们得到坐标的时候，要根据大小的顺序放入数组。 2.
因为坐标值不能为零，所以我们得到的坐标都要+1。 3.
因为有且只有一组答案符合要求，所以这大大的降低了这道题目的难度，也就是说，我们只要找到符 合条件的两个数，存入结果，直接终止程序，返回答案即可。 解题思路： 这道题不是很难，是leetcode最开始的题目，要求很明确，很直接，如果我们用两个for循环， O(n2)的时间复杂度去求解的话，很容易计算出来，但这明显不是面试官需要的答案。brute force只有在你 不知道如何优化题目的时候，将就的给出的一个解法。。那么我们能不能用O(n)的时间复杂度去解这道题 呢？很显然是可以的，不过，天下没有掉馅饼的事情啦，既然优化了时间复杂度，我们就要牺牲空间复杂 度啦。在这里用什么呢？stack？queue？vector？还是hash_map? 对于stack和queue，除了pop外，查找的时间复杂度也是O(n)。明显不是我们所需要的，那么什么数据结构 的查找时间复杂度小呢？很显然是 hash_map, 查找的时间复杂度理想情况下是O(1)。所以我们先来考虑 hash_map，看看hash_map怎么求解这个问题。 我们可以先把这个数组的所有元素存到hashmap中，一次循环就行， 时间复杂度为O(n),之后对所给数组在 进行遍历，针对其中的元素我们只要用another_number = target-numbers[i],之后用hashmap的find function来查找这个值，如果存在的话，在进行后续比较（详见代码），如果不存在的话，继续查找，好 啦，思路已经摆在这里了，详见代码吧。class Solution { public:
vector&int& twoSum(vector&int& &numbers, int target) {
//边角问题，我们要考虑边角问题的处理
vector&int& Sum13 LeetCode题解
if(numbers.size() &= 1)
//新建一个map&key,value& 模式的来存储numbers里面的元素和index，
//这里的unordered_map相当于hash_map
unordered_map&int,int& myM
for(int i = 0; i & numbers.size(); ++i)
myMap[numbers[i]] = i;
for(int i = 0; i & numbers.size(); ++i)
int rest_val = target - numbers[i];
if(myMap.find(rest_val)!=myMap.end())
int index = myMap[rest_val];
if(index == i)
//如果是同一个数字，我们就pass，是不会取这个值的
if(index & i)
ret.push_back(index+1);
//这里+1是因为题目说明白了要non-zero based index
ret.push_back(i+1);
ret.push_back(i+1);
ret.push_back(index+1);
} };以上解法的要注意的是记得要检查这两个坐标是不是相同的，因为我们并不需要同样的数字。3SumGiven an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. 题目翻译： 给定一个整型数组num，找出这个数组中满足这个条件的所有数字： num[i]+num[j]+num[k] = 0. 并且所有 的答案是要和其他不同的，也就是说两个相同的答案是不被接受的。 题目的两点要求： 1.
每个答案组里面的三个数字是要从大到小排列起来的。 2.
每个答案不可以和其他的答案相同。 题目分析： Sum 14 LeetCode题解1.
每一个答案数组triplet中的元素是要求升序排列的。 2.
不能包含重复的答案数组。 解题思路： 1.
根据第一点要求： 因为要求每个答案数组中的元素是升序排列的，所以在开头我们要对数组进行排 序。 2.
根据第二点要求： 因为不能包含重复的答案数组，所以我们要在代码里面做一切去掉重复的操作，对 于数组，这样的操作是相同的。最开始我做leetcode的时候是把所有满足条件的答案数组存起来，之后 再用map进行处理，感觉那样太麻烦了，所以这次给出的答案是不需要额外空间的。 时间复杂度分析： 对于这道题，因为是要找三个元素，所以怎样都要O(n2)的时间复杂度，目前我没有想出来O(n)时间复杂度 的解法。 归根结底，其实这是two pointers的想法，定位其中两个指针，根据和的大小来移动另外一个。解题中所要 注意的就是一些细节问题。好了，上代码吧。class Solution { public: //constant space version
vector&vector&int& & threeSum(vector&int& &num) {
vector&vector&int&&
//corner case invalid check
if(num.size() &= 2)
//first we need to sort the array because we need the non-descending order
sort(num.begin(), num.end());
for(int i = 0; i & num.size()-2; ++i)
int j = i+1;
int k = num.size()-1;
while(j & k)
vector&int&
//create a tmp vector to store each triplet which satisfy the sol
if(num[i]+num[j]+num[k] == 0)
curr.push_back(num[i]);
curr.push_back(num[j]);
curr.push_back(num[k]);
ret.push_back(curr);
//this two while loop is used to skip the duplication solution
while(j & k&&num[j-1] == num[j])
while(j & k&&num[k] == num[k+1])
else if(num[i]+num[j]+num[k] & 0)
//if the sum is less than the target value, we neeSum15 LeetCode题解
//this while loop also is used to skip the duplication solution
while(i & num.size()-1&&num[i] == num[i+1])
} };根据以上代码，我们要注意的就是用于去除重复的那三个while loop。一些细节问题比如for loop中的i & num.size()-2;因为j和k都在i后面，所以减掉两位。当然如果写成i& num.size(); 也是可以通过测试的，但感 觉思路不是很清晰。另外一点，就是不要忘记了corner case check呀。3Sum ClosestGiven an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You man assume that each input would have exactly one solution. 题目翻译： 给定一个整形数组S和一个具体的值，要求找出在这数组中三个元素的和和这个给定的值最小。input只有 一个有效答案。 题目要求： 这道题比较直接，也没有什么具体的要求。 题目分析： 1.
最短距离：两个整数的最短距离是0.这点对于这道题比较重要，别忽略。 2.
这道题和3Sum几乎同出一辙，所以方便于解题，我们还是在开头要对数组进行排序，要么没法定位指 针移动。 3.
另外，这道题中用到了INT_MAX这个值，这个值和 INT_MIN是相对应的，在很多比较求最大值最小值 的情况，经常用这两个变量。 解题思路： 这道题的解题方法和3Sum几乎相同，设定三个指针，固定两个，根据和的大小移动另外一个。属于这道题 目自己的东西就是distance比较这块儿，建立一个tmp distance和min distance比较。 时间复杂度分析： 这道题目和3Sum几乎是一个思路，所以时间复杂度为O(n2)。 代码如下： Sum 16 LeetCode题解class Solution { public:
int threeSumClosest(vector&int& &num, int target) {
//invalid corner case check
if(num.size() &= 2)
return -1;
int ret = 0;
//first we suspect the distance between the sum and the target is the largest number in int
int distance = INT_MAX;
sort(num.begin(),num.end());
//sort is needed
for(int i = 0; i & num.size()-2; ++i)
int j = i+1;
int k = num.size()-1;
while(j & k)
int tmp_val = num[i]+num[j]+num[k];
if(tmp_val & target)
tmp_distance = target - tmp_
if(tmp_distance & distance)
distance = tmp_
ret = num[i]+num[j]+num[k];
else if(tmp_val & target)
tmp_distance = tmp_val-
if(tmp_distance & distance)
distance = tmp_
ret= num[i]+num[j]+num[k];
else //note: in this case, the sum is 0, 0 means the shortest distance from the sum t
ret = num[i]+num[j]+num[k];
} };总结： 这道题的解决方法主要要注意以下几点： 1.
首先要对数组进行排序。 2.
0是两个数组间最小的距离。 Sum 17 LeetCode题解4SumGiven an array S of n integers, are there elements a, b, c and d in S such that a+b+c+d = target? Find all unique quadruplets in the array which gives the sume of target. Note: 1.
Elements in quadruplets (a, b, c, d) must be in non-descending order. (ie, a&=b&=c&=d) 2.
The solution must not contain duplicates quadruplets. 题目翻译： 给定一个整型数字数组num和一个目标值target，求出数组中所有的组合满足条件： num[a]+num[b]+num[c]+num[d] = target. 并且要满足的条件是： 1.
num[a] &= num[b] &= num[c] &= num[d] 2.
答案中的组合没有重复的. 题目分析： 这道题和3Sum几乎同出一辙，只不过是要求四个数字的和，在时间复杂度上要比3Sum高一个数量级。对 于两点要求的处理： 1.
首先要对整个数组进行排序，这样得到的答案自然是排序好的. 2.
对于重复答案的处理和3Sum是一摸一样的。 解题思路： 同3Sum. 时间复杂度分析： 这道题的解法，我选择的是空间复杂度为1， 时间复杂度为O(n3).对于这样的问题，如果到了KSum(K&=5), 我觉得可以用hash_map来牺牲空间复杂度换取好一些的时间复杂度. 代码如下：class Solution { public:
vector&vector&int& & fourSum(vector&int& &num, int target) {
vector&vector&int&&
if(num.size() &= 3) //invalid corner case check
sort(num.begin(), num.end()); //cause we need the result in quadruplets should be non-descend
for(int i = 0; i & num.size()-3; ++i)
if(i & 0 && num[i] == num[i-1])
for(int j = i+1; j & num.size()-2; ++j)
if(j & i+1 && num[j] == num[j-1])
Sum18 LeetCode题解
int k = j+1;
int l = num.size()-1;
while(k & l)
int sum = num[i]+num[j]+num[k]+num[l];
if(sum == target)
vector&int&
//create a temporary vector to store the each quadruplets
curr.push_back(num[i]);
curr.push_back(num[j]);
curr.push_back(num[k]);
curr.push_back(num[l]);
ret.push_back(curr);
//the two while loops are used to skip the duplication solutions
while(k&l && num[k] == num[k-1]);
while(k&l && num[l] == num[l+1]);
else if(sum & target)
//we can do this operation because of we sort the array at the beginnin
} };根据上述代码，我觉得要说明白的一点是: 1.
我用do{}while来代替了while进行重复答案的处理，为什么要这样呢？是因为如果换成了while， leetcode的test sample过不去，报的错误是超出了时间的限制，我认为如果要用while，应该是多进行 了++k 还有--l的操作吧。换成了do{}while就可以通过所有的test case.问题扩展 KSum根据以上的2Sum, 3Sum, 3Sum Cloest， 还有4Sum，我相信只要认真看完每道题的解法的童鞋，都 会发现一定的规律，相信这时候会有人想，如果变成KSum问题，我们应该如何求解？这是个很好的 想法，下面，我们来看看问题扩展. 首先，对于2Sum，我们用的解法是以空间复杂度来换取时间复杂度，那么，2Sum我们可不可以in place来 解？时间复杂度又是多少？ 答案是当然可以，我们可以先sort一遍，之后再扫一变，sort的时间复杂度是 O(nlogn)，扫一遍是O(n),因此，这种解法的时间复杂度是O(nlogn), 当然，如果对于要找index，leetcode上 的题不能用这个方法，因为我们sort一遍之后，index会发生一些变化。但是我们可以用以下这个function来 作为一个Helper function对于K Sum(考虑到如果K & 2, sort一遍数组的时间开销不算是主要的时间开销了):Sum19 LeetCode题解void twoSum(vector&int& &numbers, int begin, int first, int second, int target, vector&vector
if(begin &= numbers.size()-1)
int e = numbers.size()-1;
while(b & e)
int rest = numbers[b]+numbers[e];
if(rest == target)
vector&int& tmp_
tmp_ret.push_back(first);
tmp_ret.push_back(second);
tmp_ret.push_back(numbers[b]);
tmp_ret.push_back(numbers[e]);
ret.push_back(tmp_ret);
while(b&e && numbers[b] == numbers[b-1]);
while(b&e && numbers[e] == numbers[e+1]);
else if(rest & target)
}给个例子，对于4Sum，我们可以调用这个function，代码如下:class Solution { public:
void twoSum(vector&int& &numbers, int begin, int first, int second, int target, vector
if(begin &= numbers.size()-1)
int e = numbers.size()-1;
while(b & e)
int rest = numbers[b]+numbers[e];
if(rest == target)
vector&int& tmp_
tmp_ret.push_back(first);
tmp_ret.push_back(second);
tmp_ret.push_back(numbers[b]);
tmp_ret.push_back(numbers[e]);
ret.push_back(tmp_ret);
while(b&e && numbers[b] == numbers[b-1]);
while(b&e && numbers[e] == numbers[e+1]);
else if(rest & target)Sum20 LeetCode题解
vector&vector&int& & fourSum(vector&int& &num, int target) {
vector&vector&int&&
if(num.size() &= 3) //invalid corner case check
sort(num.begin(), num.end()); //cause we need the result in quadruplets should be non-descend
for(int i = 0; i & num.size()-3; ++i)
if(i & 0 && num[i] == num[i-1])
for(int j = i+1; j & num.size()-2; ++j)
if(j & i+1 && num[j] == num[j-1])
twoSum(num, j+1, num[i], num[j], target-(num[i]+num[j]), ret);
} };以上解法可以延伸到KSum.不过是相当于对于n-2个数做嵌套循环。这么写出来使得思路清晰，以后遇到了 类似问题可以解决。Sum21 LeetCode题解Find Minimum in Rotated Sorted ArraySuppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. You may assume no duplicate exists in the array. 这题要求在一个轮转了的排序数组里面找到最小值，我们可以用二分法来做。 首先我们需要知道，对于一个区间A，如果A[start] & A[stop]，那么该区间一定是有序的了。 假设在一个轮转的排序数组A，我们首先获取中间元素的值，A[mid]，mid = (start + stop) / 2。因为数组没 有重复元素，那么就有两种情况： A[mid] & A[start]，那么最小值一定在右半区间，譬如[4,5,6,7,0,1,2]，中间元素为7，7 & 4，最小元素 一定在[7,0,1,2]这边，于是我们继续在这个区间查找。 A[mid] & A[start]，那么最小值一定在左半区间，譬如[7,0,1,2,4,5,6]，这件元素为2，2 & 7，我们继续 在[7,0,1,2]这个区间查找。 代码如下:class Solution { public:
int findMin(vector&int& &num) {
int size = num.size();
if(size == 0) {
} else if(size == 1) {
return num[0];
} else if(size == 2) {
return min(num[0], num[1]);
int start = 0;
int stop = size - 1;
while(start & stop - 1) {
if(num[start] & num[stop]) {
return num[start];
int mid = start + (stop - start) / 2;
if(num[mid] & num[start]) {
} else if(num[mid] & num[start]) {
}Find Minimum in Rotated Sorted Array22 LeetCode题解
return min(num[start], num[stop]);
} };Find Minimum in Rotated Sorted ArraySuppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. The array may contain duplicates. 这题跟上题唯一的区别在于元素可能有重复，我们仍然采用上面的方法，只是需要处理mid与start相等这种 额外情况。 A[mid] & A[start]，右半区间查找。 A[mid] & A[start]，左半区间查找。 A[mid] = A[start]，出现这种情况，我们跳过start，重新查找，譬如[2,2,2,1]，A[mid] = A[start]都为2， 这时候我们跳过start，使用[2,2,1]继续查找。 代码如下:class Solution { public:
int findMin(vector&int& &num) {
int size = num.size();
if(size == 0) {
} else if(size == 1) {
return num[0];
} else if(size == 2) {
return min(num[0], num[1]);
int start = 0;
int stop = size - 1;
while(start & stop - 1) {
if(num[start] & num[stop]) {
return num[start];
int mid = start + (stop - start) / 2;
if(num[mid] & num[start]) {
} else if(num[mid] & num[start]) {
start++;Find Minimum in Rotated Sorted Array23 LeetCode题解
return min(num[start], num[stop]);
} };这题需要注意，如果重复元素很多，那么最终会退化到遍历整个数组，而不是二分查找了。Find Minimum in Rotated Sorted Array24 LeetCode题解Largest Rectangle in HistogramGiven n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area = 10 unit. For example, Given height = [2,1,5,6,2,3], return 10. 这道题目算是比较难得一道题目了，首先最简单的做法就是对于任意一个bar，向左向右遍历，直到高度小 于该bar，这时候计算该区域的矩形区域面积。对于每一个bar，我们都做如上处理，最后就可以得到最大 值了。当然这种做法是O(n2)，铁定过不了大数据集合测试的。 从上面我们直到，对于任意一个bar n，我们得到的包含该bar n的矩形区域里面bar n是最小的。我们使用ln 和rn来表示bar n向左以及向右第一个小于bar n的bar的索引位置。 譬如题目中的bar 2的高度为5，它的ln为1，rn为4。包含bar 2的矩形区域面积为(4 - 1 - 1) * 5 = 10。 我们可以从左到右遍历所有bar，并将其push到一个stack中，如果当前bar的高度小于栈顶bar，我们pop出 栈顶的bar，同时以该bar计算矩形面积。那么我们如何知道该bar的ln和rn呢？rn铁定就是当前遍历到的bar 的索引，而ln则是当前的栈顶bar的索引，因为此时栈顶bar的高度一定小于pop出来的bar的高度。 为了更好的处理最后一个bar的情况，我们在实际中会插入一个高度为0的bar，这样就能pop出最后一个bar 并计算了。Largest Rectangle in Histogram25 LeetCode题解代码如下：class Solution { public:
int largestRectangleArea(vector&int& &height) {
vector&int& s;
//插入高度为0的bar
height.push_back(0);
int sum = 0;
int i = 0;
while(i & height.size()) {
if(s.empty() || height[i] & height[s.back()]) {
s.push_back(i);
int t = s.back();
s.pop_back();
//这里还需要考虑stack为空的情况
sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
} };Largest Rectangle in Histogram26 LeetCode题解Maximal RectangleGiven a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 这题是一道难度很大的题目，至少我刚开始的时候完全不知道怎么做，也是google了才知道的。 这题要求在一个矩阵里面求出全部包含1的最大矩形面积，譬如这个：
0 1 0 0我们可以知道，最大的矩形面积为6。也就是下图中虚线包围的区域。那么我们如何得到这个区域呢？
|--------|
|--------|
0对于上面哪一题，我们先去掉最下面的一行，然后就可以发现，它可以转化成一个直方图，数据为[2, 2, 2, 0]，我们认为1就是高度，如果碰到0，譬如上面最右列，则高度为0，而计算这个直方图最大矩形面积就很 容易了，我们已经在Largest Rectangle in Histogram处理了。 所以我们可以首先得到每一行的直方图，分别求出改直方图的最大区域，最后就能得到结果了。 代码如下：class Solution { public:
int maximalRectangle(vector&vector&char& & &matrix) {
if(matrix.empty() || matrix[0].empty()) {
int m = matrix.size();
int n = matrix[0].size();
vector&vector&int& & height(m, vector&int&(n, 0));
for(int i = 0; i & m; i++) {
for(int j = 0; j & n; j++) {
if(matrix[i][j] == '0') {
height[i][j] = 0;
height[i][j] = (i == 0) ? 1 : height[i - 1][j] + 1;
}Maximal Rectangle27 LeetCode题解
int maxArea = 0;
for(int i = 0; i & m; i++) {
maxArea = max(maxArea, largestRectangleArea(height[i]));
return maxA
int largestRectangleArea(vector&int& &height) {
vector&int& s;
height.push_back(0);
int sum = 0;
int i = 0;
while(i & height.size()) {
if(s.empty() || height[i] & height[s.back()]) {
s.push_back(i);
int t = s.back();
s.pop_back();
sum = max(sum, height[t] * (s.empty() ? i : i - s.back() - 1));
} };Maximal Rectangle28 LeetCode题解Palindrome NumberDetermine whether an integer is a palindrome. Do this without extra space. 题目翻译: 给定一个数字，要求判断这个数字是否为回文数字. 比如121就是回文数字，122就不是回文数字. 解题思路: 这道题很明显是一道数学题,计算一个数字是否是回文数字，我们其实就是将这个数字除以10， 保留他的余数，下次将余数乘以10，加上这个数字再除以10的余数. 需要注意的点: 1.
负数不是回文数字. 2.
0是回文数字. 时间复杂度: logN 代码如下:class Solution { public:
bool isPalindrome(int x) {
else if(x == 0)
int tmp = x;
int y = 0;
while(x != 0)
y = y*10 + x%10;
if(y == tmp)
} };Palindrome Number29 LeetCode题解Search a 2D MatrixWrite an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example, Consider the following matrix:[
[10, 11, 16, 20],
[23, 30, 34, 50] ]题目翻译: 给定一个矩阵和一个特定值，要求写出一个高效的算法在这个矩阵中快速的找出是否这个给定的 值存在. 但是这个矩阵有以下特征. 1.
对于每一行，数值是从左到右从小到大排列的. 2.
对于每一列，数值是从上到下从小到大排列的. 题目解析: 对于这个给定的矩阵，我们如果用brute force解法，用两个嵌套循环，O(n2)便可以得到答案.但 是我们需要注意的是这道题已经给定了这个矩阵的两个特性，这两个特性对于提高我们算法的时间复杂度 有很大帮助，首先我们给出一个O(n)的解法，也就是说我们可以固定住右上角的元素，根据递增或者递减 的规律，我们可以判断这个给定的数值是否存在于这个矩阵当中.class Solution { public:
bool searchMatrix(vector&vector&int& & &matrix, int target) {
/* we set the corner case as below:
1, if the row number of input matrix is 0, we set it false
2, if the colomun number of input matrix is 0, we set it false*/
if(matrix.size() == 0)
if(matrix[0].size() == 0)
int rowNumber = 0;
int colNumber = matrix[0].size()-1;
while(rowNumber & matrix.size() && colNumber &= 0)
if(target & matrix[rowNumber][colNumber])
else if(target & matrix[rowNumber][colNumber])
}Search a 2D Matrix30 LeetCode题解};Search a 2D Matrix31 LeetCode题解Search for a RangeGiven a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 这题要求在一个排好序可能有重复元素的数组里面找到包含某个值的区间范围。要求使用O(log n)的时间， 所以我们采用两次二分查找。首先二分找到第一个该值出现的位置，譬如m，然后在[m, n)区间内第二次二 分找到最后一个该值出现的位置。代码如下：class Solution { public:
vector&int& searchRange(int A[], int n, int target) {
if(n == 0) {
return vector&int&({-1, -1});
vector&int& v;
int low = 0;
int high = n - 1;
//第一次二分找第一个位置
while(low &= high) {
int mid = low + (high - low) / 2;
if(A[mid] &= target) {
high = mid - 1;
low = mid + 1;
if(low & n && A[low] == target) {
v.push_back(low);
return vector&int&({-1, -1});
high = n - 1;
//从第一个位置开始进行第二次二分，找最后一个位置
while(low &= high) {
int mid = low + (high - low) / 2;
if(A[mid] &= target) {
low = mid + 1;
high = mid - 1;
}Search for a Range32 LeetCode题解
v.push_back(high);
} };Search for a Range33 LeetCode题解Search Insert PositionGiven a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 这题要求在一个排好序的数组查找某值value，如果存在则返回对应index，不存在则返回能插入到数组中的 index（保证数组有序）。 对于不存在的情况，我们只需要在数组里面找到最小的一个值大于value的index，这个index就是我们可以 插入的位置。譬如[1, 3, 5, 6]，查找2，我们知道3是最小的一个大于2的数值，而3的index为1，所以我们需 要在1这个位置插入2。如果数组里面没有值大于value，则插入到数组末尾。 我们采用二分法解决：class Solution { public:
int searchInsert(int A[], int n, int target) {
int low = 0;
int high = n - 1;
while(low &= high) {
int mid = low + (high - low) / 2;
if(A[mid] == target) {
} else if(A[mid] & target) {
low = mid + 1;
high = mid - 1;
} };Search Insert Position34 LeetCode题解Find Peak ElementA peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2. 这题要求我们在一个无序的数组里面找到一个peak元素，所谓peak，就是值比两边邻居大就行了。 对于这题，最简单地解法就是遍历数组，只要找到第一个元素，大于两边就可以了，复杂度为O(N)。但这 题还可以通过二分来做。 首先我们找到中间节点mid，如果大于两边返回当前index就可以了，如果左边的节点比mid大，那么我们可 以继续在左半区间查找，这里面一定存在一个peak，为什么这么说呢？假设此时的区间范围为[0, mid 1]， 因为num[mid - 1]一定大于num[mid]了，如果num[mid - 2] &= num[mid - 1]，那么num[mid - 1]就是一 个peak。如果num[mid - 2] & num[mid - 1]，那么我们就继续在[0, mid - 2]区间查找，因为num[-1]为负无 穷，所以最终我们绝对能在左半区间找到一个peak。同理右半区间一样。 代码如下：class Solution { public:
int findPeakElement(const vector&int& &num) {
int n = num.size();
if(n == 1) {
int start = 0;
int end = n - 1;
int mid = 0;
while(start &= end) {
mid = start + (end - start) / 2;
if((mid == 0 || num[mid] &= num[mid - 1]) &&
(mid == n - 1 || num[mid] &= num[mid + 1])) {
}else if(mid & 0 && num[mid-1] & num[mid]) {
end = mid - 1;
start = mid + 1;
} };Find Peak Element35 LeetCode题解Find Peak Element36 LeetCode题解Bit ManipulationBit Manipulation37 LeetCode题解Missing NumberGiven an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums =
2 . Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? 题目翻译: 从0到n之间取出n个不同的数，找出漏掉的那个。 注意：你的算法应当具有线性的时间复杂度。 你能实现只占用常数额外空间复杂度的算法吗？ 题目分析: 最直观的思路是对数据进行排序，然后依次扫描，便能找出漏掉的数字，但是基于比较的排序算 法的时间复杂度至少是 nlog(n) ，不满足题目要求。 一种可行的具有线性时间复杂度的算法是求和。对0到n求和，然后对给出的数组求和，二者之差即为漏掉 的数字。但是这种方法不适用于0是漏掉的数字的情况，因为此时两个和是相同的。（或者也能由此得出漏 掉的数字是0） 从CPU指令所耗费的时钟周期来看，比加法更高效率的运算是异或(XOR)运算。本题的标签里有位运算， 暗示本题可以用位运算的方法解决。 异或运算的一个重要性质是，相同的数异或得0，不同的数异或不为0，且此性质可以推广到多个数异或的 情形。本题的解法如下，首先将0到n这些数进行异或运算，然后对输入的数组进行异或运算，最后将两个 结果进行异或运算，结果便是漏掉的数字，因为其他数字在两个数组中都是成对出现的，异或运算会得到 0。 时间复杂度：O(n) 空间复杂度：O(1) 代码如下:class Solution { public:
int missingNumber(vector&int&& nums) {
int x = 0;
for (int i = 0; i &= nums.size(); i++) x ^= i;
for (auto n : nums) x ^= n;
} };Missing Number38 LeetCode题解Power of TwoGiven an integer, write a function to determine if it is a power of two. 题目翻译: 给出一个整数，判断它是否是2的幂。 题目分析: 2的整数次幂对应的二进制数只含有0个或者1个1，所以我们要做的就是判断输入的数的二进制表 达形式里是否符合这一条件。 有一种corner case需要注意，当输入的数为负数的时候，一定不是2的幂。 时间复杂度：O(n) 空间复杂度：O(1) 代码如下:class Solution { public:
bool isPowerOfTwo(int n) {
if (n & 0) return
bool hasOne =
while (n & 0) {
if (n & 1) {
if (hasOne) {
return hasO
} };Power of Two39 LeetCode题解Number of 1 BitsWrite a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight). For example, the 32-bit integer
has binary representation
, so the function should return 3.题目翻译: 给出一个整数，求它包含二进制1的位数。例如，32位整数 11 的二进制表达形式 是
，那么函数应该返回3。 题目分析: 设输入的数为n，把n与1做二进制的与(AND)运算，即可判断它的最低位是否为1。如果是的话， 把计数变量加一。然后把n向右移动一位，重复上述操作。当n变为0时，终止算法，输出结果。 时间复杂度：O(n) 空间复杂度：O(1) 代码如下:class Solution { public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n & 0) {
count += n & 1;
} };Number of 1 Bits40 LeetCode题解Tree树是一种重要的非线性数据结构，广泛地应用于计算机技术的各个领域。采用树可以实现一些高效地查找 算法，例如数据库系统中用到的红黑树等。 树本身的定义是递归的，因此很多涉及到树的算法通常都可以用递归的方式来实现。然而递归算法在数据 量较大的时候效率很低，所以通常会将递归改写成迭代算法。 涉及到树的题目主要包括树的遍历，平衡二叉树，查找二叉树等。Tree41 LeetCode题解Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 这题要求我们求出一个二叉树最大深度，也就是从根节点到最远的叶子节点的距离。 对于这题，我们只需要递归遍历二叉树，达到一个叶子节点的时候，记录深度，我们就能得到最深的深度 了。 代码如下：class Solution { public:
int maxDepth(TreeNode *root) {
if(!root) {
//首先初始化num为最小值
num = numeric_limits&int&::min();
travel(root, 1);
void travel(TreeNode* node, int level) {
//如果没有左子树以及右子树了，就到了叶子节点
if(!node-&left && !node-&right) {
num = max(num, level);
if(node-&left) {
travel(node-&left, level + 1);
if(node-&right) {
travel(node-&right, level + 1);
} };Minimum Depth of Binary TreeGiven a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Depth of Binary Tree 42 LeetCode题解这题跟上题几乎一样，区别在于需要求出根节点到最近的叶子节点的深度，我们仍然使用遍历的方式。 代码如下：class Solution { public:
int minDepth(TreeNode *root) {
if(!root) {
//初始化成最大值
n = numeric_limits&int&::max();
int d = 1;
depth(root, d);
void depth(TreeNode* node, int& d) {
//叶子节点，比较
if(!node-&left && !node-&right) {
n = min(n, d);
if(node-&left) {
depth(node-&left, d);
if(node-&right) {
depth(node-&right, d);
} };Depth of Binary Tree43 LeetCode题解Construct Binary Tree from Inorder and Postorder TraversalGiven inorder and postorder traversal of a tree, construct the binary tree. 要知道如何构建二叉树，首先我们需要知道二叉树的几种遍历方式，譬如有如下的二叉树：
--------|------
7前序遍历 1245367 中序遍历 4251637 后续遍历 4526731 具体到上面这一题，我们知道了一个二叉树的中序遍历以及后序遍历的结果，那么如何构建这颗二叉树 呢？ 仍然以上面那棵二叉树为例，我们可以发现，对于后序遍历来说，最后一个元素一定是根节点，也就是1。 然后我们在中序遍历的结果里面找到1所在的位置，那么它的左半部分就是其左子树，有半部分就是其右子 树。 我们将中序遍历左半部分425取出，同时发现后序遍历的结果也在相应的位置上面，只是顺序稍微不一样， 也就是452。我们可以发现，后序遍历中的2就是该子树的根节点。 上面说到了左子树，对于右子树，我们取出637，同时发现后序遍历中对应的数据偏移了一格，并且顺序也 不一样，为673。而3就是这颗右子树的根节点。 重复上述过程，通过后续遍历找到根节点，然后在中序遍历数据中根据根节点拆分成两个部分，同时将对 应的后序遍历的数据也拆分成两个部分，重复递归，就可以得到整个二叉树了。 代码如下：class Solution { public:
unordered_map&int, int& m;
TreeNode *buildTree(vector&int& &inorder, vector&int& &postorder) {
if(postorder.empty()) {
return NULL;
for(int i = 0; i & inorder.size(); i++) {
m[inorder[i]] = i;
return build(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);Construct Binary Tree44 LeetCode题解
TreeNode* build(vector&int&& inorder, int s0, int e0,
vector&int&& postorder, int s1, int e1) {
if(s0 & e0 || s1 & e1) {
return NULL;
TreeNode* root = new TreeNode(postorder[e1]);
int mid = m[postorder[e1]];
int num = mid - s0;
root-&left = build(inorder, s0, mid - 1, postorder, s1, s1 + num - 1);
root-&right = build(inorder, mid + 1, e0, postorder, s1 + num, e1 - 1);
} };这里我们需要注意，为了保证快速的在中序遍历结果里面找到根节点，我们使用了hash map。Construct Binary Tree from Preorder and Inorder TraversalGiven preorder and inorder traversal of a tree, construct the binary tree. 这题跟上面那题类似，通过前序遍历和中序遍历的结果构造二叉树，我们只需要知道前序遍历的第一个值 就是根节点，那么仍然可以采用上面提到的方式处理： 通过前序遍历找到根节点 通过根节点将中序遍历数据拆分成两部分 对于各个部分重复上述操作 代码如下：class Solution { public:
unordered_map&int, int& m;
TreeNode *buildTree(vector&int& &preorder, vector&int& &inorder) {
if(preorder.empty()) {
return NULL;
for(int i = 0; i & inorder.size(); i++) {
m[inorder[i]] = i;
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
TreeNode* build(vector&int&& preorder, int s0, int e0, vector&int& &inorder, int s1,
if(s0 & e0 || s1 & e1) {Construct Binary Tree45 LeetCode题解
return NULL;
int mid = m[preorder[s0]];
TreeNode* root = new TreeNode(preorder[s0]);
int num = mid - s1;
root-&left = build(preorder, s0 + 1, s0 + num, inorder, s1, mid - 1);
root-&right = build(preorder, s0 + num + 1, e0, inorder, mid + 1, e1);
} };可以看到，这两道题目，只要能清楚了树的几种遍历方式，以及找到如何找到根节点，并通过中序遍历拆 分成两个子树，就能很容易的搞定了，唯一需要注意的是写代码的时候拆分索引位置要弄对。Construct Binary Tree46 LeetCode题解Binary Tree Level Order TraversalGiven a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},
7return its level order traversal as:[
[15,7] ]题目翻译: 给定一颗二叉树，返回一个二维数组，使这个二维数组的每一个元素代表着二叉树的一层的元 素.例子已经明确给出. 题目分析: 对于二叉树的问题，我们第一想到的就是DFS或者BFS, DFS更易于理解代码，如果处理数据量 不是很大的话.对于这样的面试题，我建议用DFS来求解. 需要注意的点为: 1.
对于一棵树，如果我们要求每一层的节点，并且存在一个二维数组里，首先我们要建一个二维数组， 但是这个二维数组建多大的合适呢？我们就要求出这颗树的深度，根据深度来建立二维数组. 2.
题目要求为从左往右添加,所以我们也就是要先放左边的节点，再放右边的节点. 3.
对于这道题，我们首先就是要用DFS来求出这颗树的高度，之后再用DFS对于每一层遍历，这样节省 了空间复杂度. 时间复杂度分析: 由于两次DFS是并列的，并没有嵌套，所以我们的时间复杂度为O(n). 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/Binary Tree Level Order Traversal47 LeetCode题解class Solution { public: /* for this question, we need to construct the ret vector first
thus, we need to know the depth of this tree, we write a simple
function to calculate the height of this tree */
vector&vector&int& & levelOrder(TreeNode *root) {
int depth = getHeight(root);
vector&vector&int&& ret(depth);
if(depth == 0) //invalid check
getSolution(ret,root,0);
void getSolution(vector&vector&int&&& ret, TreeNode* root, int level)
if(root == NULL)
ret[level].push_back(root-&val);
getSolution(ret,root-&left,level+1);
getSolution(ret,root-&right,level+1);
int getHeight(TreeNode* root)
if(root == NULL)
int left = getHeight(root-&left);
int right = getHeight(root-&right);
int height = (left & right?left:right)+1;
} };Binary Tree Level Order Traversal IIGiven a binary tree, return the bottom-up level order traversal of its nodes' values. (from left to right, level by level from leaf to root) For example: Given binary tree {3,9,20,#,#,15,7},
7return its level order traversal as:[
[3]Binary Tree Level Order Traversal48 LeetCode题解]题目翻译: 给定一颗二叉树， 返回一个二维数组，这个二维数组要满足这个条件，二维数组的第一个一维 数组要是这可二叉树的最下面一层，之后以此类推，根据以上例子应该知道要求的条件。 题目分析 && 解题思路: 这道题和Binary Tree Level Order Traversal 几乎是一摸一样的，唯一不同的就是二 维数组的存储顺序，详见以下代码. 时间复杂度: O(n)-树的dfs均为O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
vector&vector&int& & levelOrderBottom(TreeNode *root) {
int depth = height(root);
vector&vector&int&& ret(depth);
if(depth == 0)
DFS(ret,ret.size()-1, root);
void DFS(vector&vector&int&&& ret, int level, TreeNode* root)
if(root == NULL)
ret[level].push_back(root-&val);
DFS(ret,level-1,root-&left);
DFS(ret,level-1,root-&right);
/* get the height first of all */
int height(TreeNode* root)
if(root == NULL)
int left_side = height(root-&left);
int right_side = height(root-&right);
int height = (left_side & right_side?left_side:right_side)+1;
} };Binary Tree Level Order Traversal49 LeetCode题解Binary Tree Zigzag Level Order TraversalGiven a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20,#,#,15,7},
7return its zigzag level order traversal as:[
[15,7] ]如果完成了上面两题，这题应该是很简单的，我们只需要将得到的数据按照zigzag的方式翻转一下，代码 如下：class Solution { public: vector&vector&int& &
vector&vector&int& & zigzagLevelOrder(TreeNode *root) {
build(root, 1);
for(int i = 1; i & vals.size(); i+=2) {
reverse(vals[i].begin(), vals[i].end());
void build(TreeNode* node, int level) {
if(!node) {
if(vals.size() &= level - 1) {
vals.push_back(vector&int&());
vals[level - 1].push_back(node-&val);
if(node-&left) {
build(node-&left, level + 1);
}Binary Tree Level Order Traversal50 LeetCode题解
if(node-&right) {
build(node-&right, level + 1);
} };Binary Tree Level Order Traversal51 LeetCode题解Symmetric TreeGiven a binary tree, check whether it is a mirror of itself(ie, symmetric around its center) For example, this tree is symmetric:
3But the following tree is not.
3题目翻译： 判断一棵树是不是自己的镜像， 根据以上正反两个例子，我想大家都明白这道题的题目要求 了，简单明了. 解题思路: 递归: 这道题没什么特别的地方，现在这里简单的分析一下解题思路，从根节点往下，我们要判 断三个条件. 1.
左右两个节点的大小是否相同. 2.
左节点的左孩子是否和右节点的右孩子相同. 3.
左节点的右孩子是否和右节点的左孩子相同. 循环: 这道题的难点在于循环解法， 如果是循环解法，我们必须要用到额外的存储空间用于回溯，关键是 对于这道题目， 我们要用多少？要怎么用？要用什么样的存储空间？ 递归求解，如果以上三个条件对于每一层都满足，我们就可以认为这棵树是镜像树. 时间复杂度: 递归:本质其实就是DFS,时间复杂度为O(n),空间复杂度O(1) 递归:时间复杂度O(n),空间复杂度 O(n) 递归代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };Symmetric Tree52 LeetCode题解 */ class Solution { public:
bool isSymmetric(TreeNode *root) {
if(root == NULL)
return Helper(root-&left,root-&right);
bool Helper(TreeNode* left, TreeNode* right)
if(left == NULL&&right == NULL)
else if(left == NULL||right == NULL)
bool cond1 = left-&val == right-&
bool cond2 = Helper(left-&left,right-&right);
bool cond3 = Helper(left-&right, right-&left);
return cond1&&cond2&&cond3;
} };循环解法: 我们主要想介绍一下这道题的循环解法，对于循环，我们要满足对于每一层进行check，代替了 递归，一般树的循环遍历，我们都是用FIFO的queue来作为临时空间存储变量的，所以这道题我们也选取 了queue，但是我们用两个queue，因为我们要对于左右同时进行检查，很显然一个queue是不够的，具体 实现细节，咱们还是看代码吧，，我相信代码更能解释方法. 循环代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool isSymmetric(TreeNode *root) {
if(root == NULL)
TreeNode* n1 = root-&
TreeNode* n2 = root-&
if(!n1&&!n2)
if((!n1&&n2)||(n1&&!n2))
queue&TreeNode*& Q1;
queue&TreeNode*& Q2;
Q1.push(n1);
Q2.push(n2);
while(!Q1.empty() && !Q2.empty())Symmetric Tree53 LeetCode题解
TreeNode* tmp1 = Q1.front();
TreeNode* tmp2 = Q2.front();
if((!tmp1&&tmp2) || (tmp1&&!tmp2))
if(tmp1&&tmp2)
if(tmp1-&val != tmp2-&val)
Q1.push(tmp1-&left);
Q1.push(tmp1-&right); //note: this line we should put the mirror sequence in two queu
Q2.push(tmp2-&right);
Q2.push(tmp2-&left);
} };Symmetric Tree54 LeetCode题解Same TreeGiven two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same values. 题目翻译: 给两棵树，写一个函数来判断这两棵树是否相同. 我们判定一棵树是否相同的条件为这两棵树的 结构相同，并且每个节点的值相同. 解题思路: 这道题中规中矩，很简单，我们直接用DFS前序遍历这两棵树就可以了. 时间复杂度分析: 因为是DFS, 所以时间复杂度为O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(p == NULL && q == NULL)
else if(p == NULL || q == NULL)
if(p-&val == q-&val)
bool left = isSameTree(p-&left, q-&left);
bool right = isSameTree(p-&right,q-&right);
return left&&
} };Same Tree55 LeetCode题解Balanced Binary TreeGiven a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 题目翻译: 给定一颗二叉树， 写一个函数来检测这棵树是否是平衡二叉树. 对于这个问题, 一颗平衡树的定 义是其中任意节点的左右子树的高度差不大于1. 解题思路: 这道题其实就是应用DFS，对于一颗二叉树边计算树的高度边计算差值，针对树里面的每一个节 点计算它的左右子树的高度差，如果差值大于1，那么就返回-1，如果不大于1，从下往上再次检测. 时间复杂度: 由于是运用DFS，所以时间复杂度为O(n). 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool isBalanced(TreeNode *root) {
//corner case check
if(root == NULL)
int isBalanced = getHeight(root);
if(isBalanced != -1)
int getHeight(TreeNode* root)
if(root == NULL)
int leftHeight = getHeight(root-&left);
if(leftHeight == -1)
return -1;
int rightHeight = getHeight(root-&right);
if(rightHeight == -1)
return -1;
int diffHeight = rightHeight & leftHeight? rightHeight-leftHeight:leftHeight-rightH
if(diffHeight & 1)
return -1;Balanced Binary Tree56 LeetCode题解
return diffHeight = (rightHeight&leftHeight?rightHeight:leftHeight)+1;
} };Balanced Binary Tree57 LeetCode题解Path SumGiven a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the below binary tree and sum = 22,
1return true, as there exist a root-to-leaf path 5-&4-&11-&2 which sum is 22. 题目翻译: 给定一颗二叉树和一个特定值，写一个方法来判定这棵树是否存在这样一种条件，使得从root到 其中一个叶子节点的路径的和等于给定的sum值. 解题思路: 这道题很常规，直接用DFS就可以求解. 时间复杂度: O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
bool hasPathSum(TreeNode *root, int sum) {
if(root == NULL)
return DFS(sum, 0, root);
bool DFS(int target, int sum, TreeNode* root)
if(root == NULL)
sum += root-&
if(root-&left == NULL && root-&right == NULL)
if(sum == target)
return Path Sum58 LeetCode题解
bool leftPart = DFS(target, sum, root-&left);
bool rightPart = DFS(target, sum, root-&right);
return leftPart||rightP
} };Path Sum59 LeetCode题解Binary Tree Depth Order Traversal前面我们解决了tree的level order遍历问题，这里我们需要来处理tree的depth order，也就是前序，中序和 后序遍历。Binary Tree Preorder TraversalGiven a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},
3return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? 给定一颗二叉树，使用迭代的方式进行前序遍历。 因为不能递归，所以我们只能使用stack来保存迭代状态。 对于前序遍历，根节点是最先访问的，然后是左子树，最后才是右子树。当访问到根节点的时候，我们需 要将右子树压栈，这样访问左子树之后，才能正确地找到对应的右子树。 代码如下：class Solution { public:
vector&int& preorderTraversal(TreeNode *root) {
vector&int&
if(root == NULL) {
vector&TreeNode*&
//首先将root压栈
nodes.push_back(root);
while(!nodes.empty()) {
TreeNode* n = nodes.back();
vals.push_back(n-&val);
//访问了该节点，出栈
nodes.pop_back();Binary Tree Depth Order Traversal60 LeetCode题解
//如果有右子树，压栈保存
if(n-&right) {
nodes.push_back(n-&right);
//如果有左子树，压栈保存
if(n-&left) {
nodes.push_back(n-&left);
} };Binary Tree Inorder Traversal给定一颗二叉树，使用迭代的方式进行中序遍历。 对于中序遍历，首先遍历左子树，然后是根节点，最后才是右子树，所以我们需要用stack记录每次遍历的 根节点，当左子树遍历完成之后，从stack弹出根节点，得到其右子树，开始新的遍历。 代码如下：class Solution { public:
vector&int& inorderTraversal(TreeNode *root) {
vector&int&
if(root == NULL) {
vector&TreeNode*&
TreeNode* p =
while(p || !nodes.empty()) {
//这里一直遍历左子树，将根节点压栈
while(p) {
nodes.push_back(p);
if(!nodes.empty()) {
p = nodes.back();
vals.push_back(p-&val);
//将根节点弹出，获取右子树
nodes.pop_back();
} };Binary Tree Depth Order Traversal61 LeetCode题解Binary Tree Postorder Traversal给定一颗二叉树，使用迭代的方式进行后序遍历。 对于后序遍历，首先遍历左子树，然后是右子树，最后才是根节点。当遍历到一个节点的时候，首先我们 将右子树压栈，然后将左子树压栈。这里需要注意一下出栈的规则，对于叶子节点来说，直接可以出栈， 但是对于根节点来说，我们需要一个变量记录上一次出栈的节点，如果上一次出栈的节点是该根节点的左 子树或者右子树，那么该根节点可以出栈，否则这个根节点是新访问的节点，将右和左子树分别压栈。 代码如下：class Solution { public:
vector&int& postorderTraversal(TreeNode *root) {
vector&int&
if(root == NULL) {
vector&TreeNode*&
TreeNode* pre = NULL;
nodes.push_back(root);
while(!nodes.empty()) {
TreeNode* p = nodes.back();
//如果不判断pre，我们就没法正确地出栈了
if((p-&left == NULL && p-&right == NULL) ||
(pre != NULL && (pre == p-&left || pre == p-&right))) {
vals.push_back(p-&val);
nodes.pop_back();
//右子树压栈
if(p-&right != NULL) {
nodes.push_back(p-&right);
//左子树压栈
if(p-&left != NULL) {
nodes.push_back(p-&left);
} };总结可以看到，树的遍历通过递归或者堆栈的方式都是比较容易的，网上还有更牛的不用栈的方法，只是我没 理解，就不做过多说明了。 Binary Tree Depth Order Traversal 62 LeetCode题解Binary Tree Depth Order Traversal63 LeetCode题解Populating Next Right Pointers in Each NodeGiven a binary tree
struct TreeLinkNode {
TreeLinkNode *
TreeLinkNode *
TreeLinkNode *
}Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree,
7After calling your function, the tree should look like:
2 -& 3 -& NULL
4-&5-&6-&7 -& NULL这题需要在一棵完全二叉树中使用next指针连接旁边的节点，我们可以发现一些规律。 如果一个子节点是根节点的左子树，那么它的next就是该根节点的右子树，譬如上面例子中的4，它的 next就是2的右子树5。 如果一个子节点是根节点的右子树，那么它的next就是该根节点next节点的左子树。譬如上面的5，它 的next就是2的next（也就是3）的左子树。 所以代码如下：class Solution { public:Populating Next Right Pointers in Each Node64 LeetCode题解
void connect(TreeLinkNode *root) {
if(!root) {
TreeLinkNode* p =
TreeLinkNode* first = NULL;
while(p) {
//记录下层第一个左子树
if(!first) {
first = p-&
//如果有左子树，那么next就是父节点
if(p-&left) {
p-&left-&next = p-&
//叶子节点了，遍历结束
//如果有next，那么设置右子树的next
if(p-&next) {
p-&right-&next = p-&next-&
//转到下一层
first = NULL;
} };Populating Next Right Pointers in Each Node IIWhat if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary tree,
7After calling your function, the tree should look like:
2 -& 3 -& NULLPopulating Next Right Pointers in Each Node65 LeetCode题解
4-& 5 -& 7 -& NULL不同于上一题，这题的二叉树并不是完全二叉树，我们不光需要提供first指针用来表示一层的第一个元素， 同时也需要使用另一个lst指针表示该层上一次遍历的元素。那么我们只需要处理好如何设置last的next指针 就可以了。 代码如下:class Solution { public:
void connect(TreeLinkNode *root) {
if(!root) {
TreeLinkNode* p =
TreeLinkNode* first = NULL;
TreeLinkNode* last = NULL;
while(p) {
//设置下层第一个元素
if(!first) {
if(p-&left) {
first = p-&
} else if(p-&right) {
first = p-&
if(p-&left) {
//如果有last，则设置last的next
if(last) {
last-&next = p-&
//last为left
last = p-&
if(p-&right) {
//如果有last，则设置last的next
if(last) {
last-&next = p-&
//last为right
last = p-&
//如果有next，则转到next
if(p-&next) {
//转到下一层
last = NULL;
first = NULL;Populating Next Right Pointers in Each Node66 LeetCode题解
} };其实我们可以看到，第一题只是第二题的特例，所以第二题的解法也同样适用于第一题。Populating Next Right Pointers in Each Node67 LeetCode题解Convert Sorted List to Binary Search TreeGiven a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 这题需要将一个排好序的链表转成一个平衡二叉树，我们知道，对于一个二叉树来说，左子树一定小于根 节点，而右子树大于根节点。所以我们需要找到链表的中间节点，这个就是根节点，链表的左半部分就是 左子树，而右半部分则是右子树，我们继续递归处理相应的左右部分，就能够构造出对应的二叉树了。 这题的难点在于如何找到链表的中间节点，我们可以通过fast，slow指针来解决，fast每次走两步，slow每 次走一步，fast走到结尾，那么slow就是中间节点了。 代码如下：class Solution { public:
TreeNode *sortedListToBST(ListNode *head) {
return build(head, NULL);
TreeNode* build(ListNode* start, ListNode* end) {
if(start == end) {
return NULL;
ListNode* fast =
ListNode* slow =
while(fast != end && fast-&next != end) {
slow = slow-&
fast = fast-&next-&
TreeNode* node = new TreeNode(slow-&val);
node-&left = build(start, slow);
node-&right = build(slow-&next, end);
} };Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST. 这题类似上面那题，同样地解题方式，对于数组来说，能更方便的得到中间节点，代码如下：class Solution { public:Convert Sorted List/Array to Binary Search Tree68 LeetCode题解
TreeNode *sortedArrayToBST(vector&int& &num) {
return build(num, 0, num.size());
TreeNode* build(vector&int&& num, int start, int end) {
if(start &= end) {
return NULL;
int mid = start + (end - start) / 2;
TreeNode* node = new TreeNode(num[mid]);
node-&left = build(num, start, mid);
node-&right = build(num, mid + 1, end);
} };Convert Sorted List/Array to Binary Search Tree69 LeetCode题解Path Sum IIGiven a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22.
[5,4,11,2],
[5,8,4,5] ]题目翻译： 给定一个二叉树，并且给定一个值，找出所有从根节点到叶子节点和等于这个给定值的路径.上 面的例子可以很好地让读者理解这个题目的目的. 解题思路: 这个题目和Path Sum的解法几乎是一模一样，都是用dfs来进行求解，不过就是在传参数的时候 有些不同了，因为题目的要求也不同. 时间复杂度: O(n) 代码如下:/**
* Definition for binary tree
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
vector&vector&int& & pathSum(TreeNode *root, int sum) {
vector&vector&int&&
if(root == NULL)
vector&int&
DFS(ret,curr,sum,0,root);Path Sum II70 LeetCode题解
void DFS(vector&vector&int&&& ret, vector&int& curr, int sum, int tmpsum, TreeNode* root)
if(root == NULL)
tmpsum+=root-&
curr.push_back(root-&val);
if(tmpsum == sum)
if(root-&left == NULL&&root-&right == NULL)
ret.push_back(curr);
DFS(ret,curr,sum,tmpsum,root-&left);
DFS(ret,curr,sum,tmpsum,root-&right);
} };Path Sum II71 LeetCode题解Flatten Binary Tree to Linked ListGiven a binary tree, flatten it to a linked list in-place. For example, Given
6The flattened tree should look like:
6给定一颗二叉树，将其扁平化处理，我们可以看到处理之后的节点顺序其实跟前序遍历原二叉树的一致， 所以我们只需要前序遍历二叉树同时处理就可以了。代码如下：class Solution { public:
void flatten(TreeNode *root) {
if(!root) {
TreeNode dummy(0);
TreeNode* n = &
ns.push_back(root);
while(!ns.empty()) {
TreeNode* p = ns.back();
ns.pop_back();
//挂载到右子树
n-&right = p;
n = p;Flatten Binary Tree to Linked List72 LeetCode题解
//右子树压栈
if(p-&right) {
ns.push_back(p-&right);
p-&right = NULL;
//左子树压栈
if(p-&left) {
ns.push_back(p-&left);
p-&left = NULL;
} };Flatten Binary Tree to Linked List73 LeetCode题解Validate Binary Search TreeGiven a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. 这题需要判断是不是一个正确的二叉搜索树，比较简单地一道题。 我们通过递归整棵树来解决，代码如下：class Solution { public:
bool isValidBST(TreeNode *root) {
return valid(root, numeric_limits&int&::min(), numeric_limits&int&::max());
bool valid(TreeNode* node, int minVal, int maxVal) {
if(!node) {
if(node-&val &= minVal || node-&val &= maxVal) {
return valid(node-&left, minVal, node-&val) &&
valid(node-&right, node-&val, maxVal);
} };Validate Binary Search Tree74 LeetCode题解Recover Binary Search TreeTwo elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? 这题需要修复一颗二叉搜索树的两个交换节点数据，我们知道对于一颗二叉搜索树来说，如果按照中序遍 历，那么它输出的值是递增有序的，所以我们只需要按照中序遍历输出，在输出结果里面找到两个异常数 据（比它后面输出结果大），交换这两个节点的数据就可以了。 但是这题要求使用O(1)的空间，如果采用通常的中序遍历（递归或者栈）的方式，都需要O(N)的空间，所 以这里我们用Morris Traversal的方式来进行树的中序遍历。 Morris Traversal中序遍历的原理比较简单： 如果当前节点的左孩子为空，则输出当前节点并将其有孩子作为当前节点。 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点，也就 是当前节点左子树的最右边的那个节点。 如果前驱节点的右孩子为空，则将它的右孩子设置为当前节点，当前节点更新为其左孩子。 如果前驱节点的右孩子为当前节点，则将前驱节点的右孩子设为空，输出当前节点，当前节点更 新为其右孩子。 重复上述过程，直到当前节点为空，递归的时候我们同时需要记录错误的节点。那么我们如何知道一个节 点的数据是不是有问题呢？对于中序遍历来说，假设当前节点为cur，它的前驱节点为pre，如果cur的值小 于pre的值，那么cur和pre里面的数据就是交换的了。 代码如下：class Solution { public:
void recoverTree(TreeNode *root) {
TreeNode* cur = 0;
TreeNode* pre = 0;
TreeNode* p1 = 0;
TreeNode* p2 = 0;
TreeNode* preCur = 0;
bool found =
if(!root) {
while(cur) {
if(!cur-&left) {Recover Binary Search Tree75 LeetCode题解
//记录p1和p2
if(preCur && preCur-&val & cur-&val) {
if(!found) {
cur = cur-&
pre = cur-&
while(pre-&right && pre-&right != cur) {
pre = pre-&
if(!pre-&right) {
pre-&right =
cur = cur-&
//记录p1和p2
if(preCur-&val & cur-&val) {
if(!found) {
pre-&right = NULL;
cur = cur-&
if(p1 && p2) {
int t = p1-&
p1-&val = p2-&
p2-&val = t;
} };Recover Binary Search Tree76 LeetCode题解Binary Tree PathGiven a binary tree, return all root-to-leaf paths. For example, given the following binary tree:
5All root-to-leaf paths are:[&1-&2-&5&, &1-&3&]题目翻译： 给定一棵二叉树，返回所有从根节点到叶节点的路径。 题目分析： 本题属于二叉树的遍历问题，可以用深度优先搜索来解决。 使用栈来记录遍历过程中访问过的节点。递归地访问每个节点的子节点，如果遇到叶节点，则输出记录的 路径。返回上一层之前弹出栈顶元素。 C++的vector容器也能做到后进先出，所以下面的代码并没有使用 std::stack类来实现。 生成输出的字符串时，可以使用std::stringstream类来完成，类似于Java和C#中的StringBuilder。/**
* Definition for a binary tree node.
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
vector&string& binaryTreePaths(TreeNode* root) {
vector&string&
if (root == nullptr) return
vector&int&
bfs(root, path, result);
} private:
// 递归函数，深度优先搜索
void bfs(TreeNode* node, vector&int&& path, vector&string&& result) {
if (node == nullptr)
path.push_back(node-&val);Binary Tree Path77 LeetCode题解
if (node-&left == nullptr && node-&right == nullptr)
result.push_back(generatePath(path));
if (node-&left != nullptr) {
bfs(node-&left, path, result);
path.pop_back();
if (node-&right != nullptr) {
bfs(node-&right, path, result);
path.pop_back();
// 辅助函数，用于生成路径字符串
string generatePath(vector&int& path) {
stringstream
for (i = 0; i & path.size() - 1; i++) ss && path[i] && &-&&;
ss && path[i];
return ss.str();
} };Binary Tree Path78 LeetCode题解Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path
which represents the number
123 . Find the total sum of all root-to-leaf numbers. For example,
3The root-to-leaf path
represents the number
12 . The root-to-leaf path
represents the number
13 . Return the sum = 12 + 13 = 25. 题目翻译： 给定一棵二叉树，仅包含0到9这些数字，每一条从根节点到叶节点的路径表示一个数。例如， 路径 1-&2-&3 表示数值123。求出所有路径表示的数值的和。 上述例子中，路径 1-&2 表示数值12，路 径 1-&3 表示数值13。它们的和是25。 题目分析: 从根节点到叶节点的遍历方法是深度优先搜索(DFS)。解决本题只需在遍历过程中记录路径中的 数字，在到达叶节点的时候把记录下来的数字转换成数值，加到和里面即可。 时间复杂度: O(n) 代码如下:/**
* Definition for a binary tree node.
* struct TreeNode {
TreeNode *
TreeNode *
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
*/ class Solution { public:
int sumNumbers(TreeNode* root) {
vector&int&
int sum = 0;
dfs(root, arr, sum);
int vec2num(vector&int&& vec) {
int num = 0;
for (auto n : vec) {
num = num * 10 + n;
}Sum Root to Leaf Numbers79 LeetCode题解
void dfs(TreeNode* node, vector&int&& arr, int& sum) {
if (node == nullptr)
arr.push_back(node-&val);
if (node-&left == nullptr && node-&right == nullptr) {
sum += vec2num(arr);
if (node-&left != nullptr) dfs(node-&left, arr, sum);
if (node-&right != nullptr) dfs(node-&right, arr, sum);
arr.pop_back();
} };Sum Root to Leaf Numbers80 LeetCode题解Dynamic ProgrammingDynamic Programming81 LeetCode题解Best Time to Buy and Sell StockSay you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.}
我要回帖
更多推荐
- ·我们是一家电商推广平台平台，预计会有大量订单爆发式增长，成都是否有云仓能满足这种需求？
- ·2024年现在做跨境电商怎么样领域还存在哪些蓝海市场？
- ·影响消费者购买决策的因素有哪些没有适应零售模式的变革，对于企业来说有怎样的影响？
- ·如何简化跨境电商收款方式有哪些流程？
- ·朗逸1.6手动挡价格手动舒适版1.6好吗？
- ·p3led显示屏价格p3规格尺寸/10平方p3全彩显示屏多少钱
- ·如何愉快地串口调试工具 for mac一个 React Native for Android APP
- ·腾达路由器端口映射不成功映射端口不成功
- ·cdc1-25-30-10接触器与cjx8-25-30-10交流接触器功能和用途是一样吗
- ·外盘期货交易平台一般用的什么交易软件
- ·美团饿了么、拼多多、饿了么和一拼网哪个好？
- ·c#中的String.IsNullOrWhiteSpace(aa) 是否等同于Javaabo中的aaa!=null &&aa!=""，如果不是的话，等同于什么
- ·h里番动漫百度云网盘之家的网盘分享区gg了吗，怎么登陆不了？求
- ·xzp小米进水开机无限重启了 怎么办.司机 重启一半 就不能开机了
- ·华为p10和苹果7哪个好8买哪个呀，大家给个意见
- ·php wampserverr怎么切换php版本
- ·怎么在controller新建websocket 链接状态链接
- ·CSS怎么我的世界电脑联机平台联机平台啊，一般是什么平台
- ·mysql bin目录在哪data下面目录下有很多mysql-bin的文件，能删除吗
- ·leetcode 从一个string到另一个string最少需要string找到int多少次修改
- ·小米笔记本网线接口4a 32寸 可以插网线吗
- ·Python中threading setdaemon的join和setDaemon的区别及用法
- ·微信设置功能里没有朋友圈圈
- ·nodejs部署到tomcat怎样向tomcat服务器提交ajax请求
- ·谁知道他李宏毅他哥的快手号号
- ·如何在vuejs中使用vue.js和bootstrapp
- ·雷诺尔安川变频器anchuanbpqrgs bpq rcs 什么意思
- ·怎样能把Arduino上的qt程序移植到开发板STM8上
- ·为什的我的pr缺少渲染器什么意思一直重复渲染
- ·如何在JPA的po类中调用存储过程中调用函数和函数
- ·有没有人买过flower flowerplus花加加啊？花好吗
- ·买电脑桌去哪买实体店好还是网上的好
- ·下面一行代码代码重构是什么意思思？
- ·大家来说说电脑都来买什么样的人
