LEETCODE学习记录(数组+位运算+树)

# 1.数组(Array)
## 1.2 移除元素(27-th:Remove Element)
 - `题目要求`
- 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
- 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地 修改输入数组。
- 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 - `测试样例`:
```
- 给定 nums = [3,2,2,3], val = 3,

- 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
```
- 你不需要考虑数组中超出新长度后面的元素。
 - `个人参考代码`：
```
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int length =nums.size();
        int i=0,j=0;
        for(;i<length;i++)
        {
            if(nums[i]!=val)
            {
              nums[j] = nums[i];
              j++;
            }
        }
        return j;
    }
};
```
## 1.3.1 删除排序数组中的重复项
(26th:Remove Duplicates from Sorted Array)
 - `题目要求`
- 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

- 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

- `测试样例`
```
给定 nums = [0,0,1,1,1,2,2,3,3,4],

- 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
```
- 你不需要考虑数组中超出新长度后面的元素。

- `参考代码`
```
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
     //sorted array: nums[i+1]>=nums[i]
     int i,j;
     int length =nums.size();
    for(i=0,j=0;i<length;i++)
     {
        while((i<length-1)&&nums[i+1]==nums[i])
        {
          i++;
        }
        nums[j] =nums[i];
        j++;
     }
     return j;
    }
};
```
##1.3.2 删除排序数组中的重复项II
(Remove Duplicates from Sorted Array II)
 - `题目要求`
- 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

- 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

- `测试用例`
```
- 给定 `nums = [0,0,1,1,1,1,2,3,3],`

- 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
```
- 你不需要考虑数组中超出新长度后面的元素。

- `参考代码`
```
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i,j;
        int length =nums.size();
        for(i=0,j=0;i<length;i++)
        {
            //remove duplicates
            int dup_cnt =1;
            while(i<(length-1) && nums[i+1]==nums[i])
            {
                i++;
                dup_cnt++;
            }
            if(dup_cnt>=2)
            {
             nums[j]=nums[i];
             nums[j+1]=nums[i];
             j+=2;
            }
            else
            {
            //modifying the input array in-place
            nums[j]=nums[i];
            j++;
            }
        }
        return j;
    }
};
```
## 1.4 加一
(66th: Plus One)
 - `题目要求`
- 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

- 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

- 你可以假设除了整数 0 之外，这个整数不会以零开头。

- `测试用例`
```
- 输入: [4,3,2,1]
- 输出: [4,3,2,2]
- 解释: 输入数组表示数字 4321。
```
 - `参考代码`
```
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
       int carry_bit =1;
       for(int i =digits.size()-1;i>=0;i--)
       {
           int current_val =digits[i]+carry_bit;
           carry_bit =current_val/10;
           digits[i] =current_val%10;
       }
       
       if(carry_bit>0)
       {
           digits.insert(digits.begin(),carry_bit);
       }
       return digits;
    }
};
```
## 1.5 杨辉三角I & II
(118-th && 119-th: Pascal's Triangle)
 - `题目要求`
- 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
- 在杨辉三角中，每个数是它左上方和右上方的数的和。
 - `测试用例`
```
- 输入: 5
- 输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
```
 - `参考代码`
```
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> pascal_delta;
        if(numRows<=0)
        {
            return pascal_delta;
        }
        vector<int> last_row(1,1);
        for(int i=0;i<numRows;i++)
        {
           vector<int> tmp_row(i+1,1);
           for(int j = 0; j<i+1;j++)
           {
             if(j==0 || j==i){
                 tmp_row[j]=1;
             }
             else
             {
                 tmp_row[j] = last_row[j-1]+last_row[j];
             }
           }
           last_row =tmp_row;
           pascal_delta.push_back(tmp_row);;
        }
       return pascal_delta;
    }
};
```
119题要求:给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。代码如下：
```
class Solution {
public:
    vector<int> getRow(int rowIndex) 
    { 
       vector<int> last_row(1,1);
       for(int i=0;i<=rowIndex;i++)
       {
           vector<int> current_row(i+1,1);
           for(int j=0;j<=i;j++)
           {
               if(j==0 || j==i)
               {
                   current_row[j]=1;
               }
               else
               {
                   current_row[j] = last_row[j-1] + last_row[j];
               }
            //    if(i == rowIndex && j==i)
            //    {
            //       //It is not recommended,Don't return here!!!
            //        return current_row;
            //    }
            }
            last_row =current_row;
        }
        return last_row;
    }    
};
```
## 1.6 合并两个有序数组
(88-th:Merge Sorted Array)
 - `题目要求`
- 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 - `测试用例`
```
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]
```
 - `参考代码`
```
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        //when nums1 is null
        if(m<=0)
        {
           nums1 =nums2;
        }
        //do only when n>0
        if(n>0)
        {
        //from tail to head
        int i=m-1,j=n-1,k=m+n-1;
        while(k>=0)
        {   
            //choose element from nums1
            if(j>=0&&i>=0&&nums1[i]>nums2[j] || j<0&&i>=0){
                nums1[k] = nums1[i];
                i--;
                k--;
            }
            //choose element from both nums1 and nums2
            else if(i>=0&&j>=0&&nums1[i]==nums2[j]){
                nums1[k]=nums1[i];
                nums1[k-1]=nums2[j];
                i--;
                j--;
                k-=2;
            }
            //choose elment from nums2
            else if(j>=0&&i>=0&&nums1[i]<nums2[j] || j>=0&&i<0){
                nums1[k] = nums2[j];
                j--;
                k--;
            }
        }
    }
}
};
```
## 1.7 两数之和
(1st:two sum)
 - `题目要求`
- 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
- 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 - `测试用例`
```
 给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9, 所以返回 [0, 1]
```
 - `参考代码`
- 这里我们使用hashmap加速: 
```
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> indices;
        //key:original nums,value:indices
        unordered_map<int,int> hash_map; 
        for(int i=0;i<nums.size();i++)
        {
            hash_map[nums[i]] =i;
        }

for(int i=0;i<nums.size();i++)
        {
            int rest_val = target - nums[i];
            //try to find the rest_val in hash_map
            if(hash_map.find(rest_val)!=hash_map.end())
            {
                int index = hash_map[rest_val];
                //can't use the same element twice
                if(index==i)
                    continue;
                indices.push_back(index<i?index:i);
                indices.push_back(index<i?i:index);
                break;                
            }

}
        return indices;
    }
};
```
## 1.8 三数之和
（15-th:3sum）
 - `题目要求`
- 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
- 注意：答案中不可以包含重复的三元组。

- `测试用例`
```
- 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

- 满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
```
 - `参考代码`
```
 class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
     //Sort the nums，default ascending sort
     sort(nums.begin(),nums.end());
     vector<vector<int>> res_vec;
     int k,i,j;
     int length = nums.size();
     for(k=0;k<length-2;)
     {
        for(i=k+1,j=length-1;i<j;)
        {
           int tmp_val = nums[i]+nums[j];
           //too large
           if(nums[k]+tmp_val>0)
           {
             j--;
             while(i<j&&nums[j+1]==nums[j])
             {
                j--;
             }   
           }
           //too small
           else if(nums[k]+tmp_val<0)
           {
             i++;
             while(i<j&&nums[i-1]==nums[i])
             {
                 i++;
             }
           }
           else{
             vector<int> tmp_vec = {nums[k],nums[i],nums[j]};
             res_vec.push_back(tmp_vec);
             //indices duplicate removal
             j--;
             while(i<j&&nums[j+1]==nums[j])
             {
                j--;
             }
             i++;
             while(i<j&&nums[i-1]==nums[i])
             {
                 i++;
             }
           }
        }
        k++;
        while(k<length-2&&nums[k-1]==nums[k])
        {
            k++;
        }
     }
    return res_vec;  
    }
};
```
## 1.8 最接近的三数之和
(16. 3Sum Closest)
 - `题目要求`
- 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
- 找出 nums 中的三个整数，使得它们的和与 target 最接近。
- 返回这三个数的和。假定每组输入只存在唯一答案。

- `测试用例`
```
给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2.  (-1 + 2 + 1 = 2).
```
 - `参考代码`

```
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int res_sum =nums[0]+nums[1]+nums[2];
        int length = nums.size();
        //three pointer indices
        int k,i,j;
        for(k = 0;k<length-2;)
        {
            for(i=k+1,j=length-1;i<j;)
            {
                int temp_val =nums[k]+nums[i]+nums[j];
                //too large
                if(temp_val>target)
                {

if(abs(res_sum-target)>abs(temp_val-target))
                    {
                        res_sum = temp_val;
                    }
                    j--;
                    while(i<j&&nums[j+1]==nums[j])
                    {
                        j--;
                    }
                }
                //too small
                else if(temp_val<target)
                {
                    //int temp_val=nums[k]+nums[i]+nums[j];
                    if(abs(res_sum-target)>abs(temp_val-target))
                    {
                        res_sum=temp_val;
                    }
                    i++;
                    while(i<j&&nums[i-1]==nums[i])
                    {
                        i++;
                    }
                }
                //exactly equals to tartget
                else
                {
                   res_sum = temp_val;
                   break;
                }
            }
            k++;
            while(k<length-2 && nums[k-1]==nums[k])
            {
                k++;
            }
        }
    return res_sum;
    }
};
```
## 1.9 四数之和(18th:4Sum)
 - `题目要求`
- 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
- 注意：答案中不可以包含重复的四元组。

- `测试用例`
```
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
- 满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
```
 - `参考代码`
```
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int> > res_nums;
		sort(nums.begin(), nums.end());
		for (int k = nums.size() - 1; k >= 3;)
		{
			for (int h = 0;k >= h + 3;)
			{
				for (int i = h + 1, j = k - 1; i < j;)
				{

int tmp_sum = nums[i] + nums[j];
					if (tmp_sum + nums[h] + nums[k] < target)
					{//小于0则让i增加,从而让nums[i]增加
						i++;
                        //while(nums[i-1]==nums[i]&&i<j)
                        //{
                        //    i++;
                        //}
					}
					else if (tmp_sum + nums[h] + nums[k] > target) {
						//大于0则让j减少
						j--;
                        //while(nums[j+1]==nums[j]&&i<j)
                        //{
                        //    j--;
                        //}
					}
					else { //等于0,则先保存i,j,k对应的值,同时移动ij,去除掉重复的值
						vector<int> tmp_vec;
						tmp_vec.push_back(nums[h]);
						tmp_vec.push_back(nums[i]);
						tmp_vec.push_back(nums[j]);
						tmp_vec.push_back(nums[k]);
						res_nums.push_back(tmp_vec);
						//去重复
						i++;
						while (i < j &&nums[i - 1] == nums[i]) {
							i++;
						}
						j--;
						while (i < j &&nums[j + 1] == nums[j]) {

j--;
						}
					}

}
				//去掉重复的h
				h++;
				while (k >= h + 3 && nums[h - 1] == nums[h])
				{
					h++;
				}
			}
			//去掉重复的k
			k--;
			while (k >= 3 && nums[k + 1] == nums[k])
			{
			    k--;
			}

}
		return res_nums;
    }
};
```
## 1.10 寻找旋转排序数组中的最小值(以及特定值)I&&II
- `1.题目要求(153&&154. Find Minimum in Rotated Sorted Array)`
    - 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
    ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
    - 请找出其中最小的元素。
    - 你可以假设数组中不存在重复元素。
    - `测试用例`
    ```
    输入: [4,5,6,7,0,1,2]
    输出: 0
    ```
    - `参考代码`
采用二分法，这里比较的是左边界，实际上比较右边界更简单，因为比较右边界不怕[1,2,3,4]这样的特殊情况：
```
class Solution {
public:
    int findMin(vector<int>& nums) {
        int length= nums.size();
        int left = 0,right = length-1,mid;
        while(left<right-1)
        {
           //This “is” can be removed if compare with right edge
           if(nums[left]<nums[right])
           {
               return nums[left];
           }
           mid = left + (right-left)/2;
           //locates in left area
           if(nums[left]>nums[mid]){
              right = mid;
           }
           //locates in right area
           else if(nums[left]<=nums[mid]){
              left = mid;
           }
        }
        return nums[left]<nums[right]?nums[left]:nums[right];
    }
};
```
- 2.leetcode154题
    - 该题则需要考虑数组中可能存在重复的情况,这里就是比较的右边界：
```
class Solution {
public:
    int findMin(vector<int>& nums) {
        int minimum = nums[0];
        int lef =0,rit = nums.size()-1,mid;
        // while(lef<rit-1)
        // {
        //    mid = lef + (rit - lef)/2;
        //    //minimum locates in left area
        //    if(nums[mid]<nums[rit]){
        //       rit = mid;
        //    }
        //    //minimum locates in right area
        //    else if(nums[mid]>nums[rit]){
        //       lef = mid;
        //    }
        //    //not sure,so let right pointer reduce 
        //    else{
        //       rit--; 
        //       while(lef<rit-1 && nums[rit-1]==nums[rit])
        //       {
        //           rit--;
        //       }
        //    }
        // }
        // return nums[lef]<nums[rit]?nums[lef]:nums[rit];

while(lef<rit)
        {
            mid = lef + (rit - lef)/2;
            if(nums[mid]<nums[rit])
            {
                rit = mid;
            }
            else if(nums[mid]>nums[rit])
            {
                lef = mid + 1;
            }
            else
            {
                rit--;
                while(lef<rit-1 && nums[rit-1]==nums[rit])
                {
                    rit--;
                }
            }
        }
        return nums[lef];
    }
};
```
- 3.leetcode33题
    - 该题则要求找旋转数组中的特定值：
```
假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1
示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0
https://leetcode-cn.com/problems/find-minimum-in-rot
```
```
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int left = 0,right = nums.size()-1,mid = left + (right - left)/2;
        int minidx = 0;
        //先找到最小点，最小点即为旋转点，然后进行二分查找
        while(left < right)
        {
            mid = left + (right - left)/2;
            if(nums[mid] > nums[right])
            {
                left = mid + 1;
            }
            else if(nums[mid] <= nums[right])
            {
                right = mid;
            }
        }
        //minidx为旋转点
        minidx = left;
        //相当于没旋转
        if(minidx == 0)
        {
            return findMin(nums,minidx,nums.size()-1,target);
        }
        else
        {   
            //分情况再使用二分查找
            if(nums[nums.size()-1] < target)
            {
                return findMin(nums,0,minidx-1,target);
            }
            else
            {
                return findMin(nums,minidx,nums.size()-1,target);
            }
        }
        return 0;
    }
private:
    int findMin(vector<int>& nums,int left,int right,int target)
    {
        int mid = left + (right - left)/2;
        while(left <= right)
        {
            mid = left + (right - left)/2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }
            else if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else return mid;
        }
        return -1;
    }
};
```
##1.11柱状图中最大的矩形
 - `题目要求(84. Largest Rectangle in Histogram)`
- 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

- 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 - `测试用例`
```
输入: [2,1,5,6,2,3]
输出: 10
```
 - `参考代码`
 利用单调栈解题：
```
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        heights.insert(heights.begin(),0);
        stack<int> stk;
        int max_area = 0; 
        for(int i =0;i<heights.size();i++)
        {
            while(!stk.empty() && heights[i]<heights[stk.top()])
            {
                //computing area for bar i-1
                int top_index = stk.top();
                stk.pop();
                max_area = max(max_area,heights[top_index]*(i - stk.top()-1));
            }
            stk.push(i);
        }
        return max_area;
    }
};
```
## 1.12 最大矩形
(85th:Maximal Rectangle)
 - `题目要求`
- 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 - `测试用例`
```
输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6
```
 - `参考代码`
将本问题简化成前一个问题即可：
```
class Solution {
public:
    int maxHistRect(vector<int>& heights)
    {
        int max_area = 0;
        heights.push_back(0);
        heights.insert(heights.begin(),0);
        stack<int> stk;
        for(int i=0;i<heights.size();i++)
        {
            while(!stk.empty() && heights[i] < heights[stk.top()])
            {
                 int curr_index = stk.top();
                 stk.pop();
                 max_area = max(max_area,heights[curr_index]*(i - stk.top()-1));
            }
            stk.push(i);
        }
        //恢复heights,如果不引用传参则不需要
        heights.pop_back();
        heights.erase(heights.begin());
        return max_area;
    }

int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty() || matrix[0].empty())
          {
              return 0;
          }
        int max_area = 0;
        //转化成直方图
        int h = matrix.size();
        int w = matrix[0].size();
        vector<int> heights(w,0); 
        //对其中每行均求解最大矩形,类似84题
        for(int i = 0;i<h;i++)
        {
            for(int j=0;j<w;j++)
            {
                if(matrix[i][j] == '0') heights[j] = 0;
                else heights[j]++;
            }
            max_area =max(max_area,maxHistRect(heights));
        }
    return max_area;
    }
};
```
## 1.13 盛最多水的容器
```
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

链接：https://leetcode-cn.com/problems/container-with-most-water
。
```
```
示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
```
```
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0;
		for(int i = 0, j = height.size() - 1; i < j ; )
        {
            //双指针高度较低的
            int minHeight =0;
            if(height[i]<height[j])
            {
                 minHeight =height[i];
                 i++;
            }
            else
            {
                 minHeight =height[j];
                 j--;
            }
			//int minHeight = height[i] < height[j] ? height[i++] : height[j --];
            if(max<(j - i + 1) * minHeight)
            {
                 max =(j - i + 1) * minHeight;
            }    
		}
		return max;
    }
};
```
## 1.15 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
```
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
https://leetcode-cn.com/problems/trapping-rain-water/
```
技巧性解答:
```
class Solution {
public:
    int trap(vector<int>& height) {
        //想象有水平光线,从左向右以及从右向左地往中间照射
        //那么光线照射不到的区域面积,就是雨水量
    	int sum_rain = 0;  //雨水量
		int max_height = 0;
		int n_height = height.size();

//if (height.begin() != height.end()) 
		//{
		//	max_height = *max_element(height.begin(), height.end());
		//}
		//else 
		//{
		//	max_height = 0;
		//}
		for (int i = 0; i < n_height; i++)
		{
			if (height[i] > max_height) {
				max_height = height[i];
		 }
		}

int sum_area = max_height * n_height;
		int light_area = 0;
		int stone_area = 0;

//左边阳光照射
		for (int i = 0; i < max_height; i++)
		{
			int n = 0;

while (n<n_height && (max_height - i) > height[n]) 
            {

light_area++;
				n++;
				
			}

}
		//右边阳光照射
		for (int i = 0; i < max_height; i++) {

int n = n_height - 1;
			while (n >= 0 && (max_height - i) > height[n])
			{
				light_area++;
				n--;
			
			}

}
		//计算原始的数组面积,相当于求围"水坝的石头面积"
		for (int i = 0; i < n_height; i++)
		{
			stone_area += height[i];
		}

sum_rain = sum_area - light_area - stone_area;

return sum_rain;
    }
};
```
单调栈解答:
```
class Solution {
public:
    int trap(vector<int>& height) {
         //单调栈,从栈底到栈顶递减
         stack<int> stk;
         int total_rain = 0;
         for(int i = 0;i<height.size();i++)
         {
            while(!stk.empty()&& height[i] > height[stk.top()])
            {
                int curr_index =stk.top();
                stk.pop();
                if(!stk.empty())
                {
                   total_rain+= (min(height[i],height[stk.top()]) - height[curr_index])*(i - stk.top()-1);
                }
            }
            stk.push(i);
         }
        return total_rain;
    }
};
```
##1.13 回文数
 - `题目要求(9. Palindrome Number)`
- 判断一个整数是否是回文数。
- 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
`测试用例`
```
示例 1:
  输入: 121
  输出: true
示例 2:
  输入: -121
  输出: false
  解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
```
 - `参考代码`
 可以转为字符串流处理，更好的方式是直接取余计算：
```
class Solution {
public:
    bool isPalindrome(int x) {
		// if (x < 0) {
		// 	return false;
		// }
		// string x_str;
		// stringstream ss;
		// ss << x;
		// ss >> x_str;   //或者 trans = ss.str();
		// string re_x_str;
		// for (int i =x_str.size()-1;i>=0; i--)
		// {
		// 	re_x_str.push_back(x_str[i]);
		// }
		// return re_x_str ==x_str;

if(x<0) return false;
        else{
             int prime = x;
             long int y = 0;
             while(!x==0)
             {
                 y = x%10 + y*10; //y保存所有的余数
                 x = x/10;
             }
             return y==prime;
        }
    }
};
```

##1.14 搜索二维矩阵(数组)
 - `题目要求(74. Search a 2D Matrix)`
- 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
 - `测试用例`
- 输入:
```
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
- 输出: true
```
 - `参考代码`
有很多人的代码速度为O(n),虽然比较简单,但是理论上本题最快的是二分法，O(logn)，如下。不过更简单的二分法，应该是把矩形展成一条线，直接二分比较.
```
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        return func2(matrix,target);
    }
private:
    //二分法：有点小麻烦，推荐第二种写法
    bool func1(vector<vector<int>> &matrix,int target)
    {
        int m = matrix.size();
        if(m==0)
        {
            return false; 
        }
        int n = matrix[0].size();
        if(n==0)
        {
            return false;
        }

int low_idx = 0,high_idx = matrix.size(),center_idx = low_idx + (high_idx - low_idx)/2;
        int search_idx = 0;

int lef = 0,rit = matrix[0].size()-1,mid = lef + (rit - lef)/2;
        //找到对应的行
        while(low_idx < high_idx - 1)
        {
            center_idx = low_idx + (high_idx - low_idx)/2;
            if(matrix[center_idx][0] < target)
            {
                low_idx = center_idx;
            }
            else if(matrix[center_idx][0] > target)
            {
                high_idx = center_idx;
            }
            else
            {
                return true;
            }
        }
        
        //最后一行比较特殊
        if(matrix[m-1][0] < target)
        {
            low_idx =m-1;
        }

while(lef < rit)
        {
            mid = lef + (rit - lef)/2;
            if(matrix[low_idx][mid] < target)
            {
                lef = mid + 1;
            }
            else if(matrix[low_idx][mid] > target)
            {
                rit = mid - 1;
            }
            else
            {
                return true;
            }
        }
        if(matrix[low_idx][lef] == target)
          return true;
        else return false;
    }   
    //二分法：不过是将矩形拉成一条直线来直接二分的，代码更简洁 
    bool func2(vector<vector<int>> &matrix,int target)
    {
        int m = matrix.size();
        if(m==0) return false; 
        int n = matrix[0].size();
        if(n==0) return false;
        int left = 0,right = m*n-1,mid = left + (right - left)/2;
        // while(left < right-1)
        while(left<right)
        {
            mid = left + (right - left)/2;
            if(matrix[mid/n][mid%n] < target)
            {
                //left = mid;
                left = mid+1;
            }else if(matrix[mid/n][mid%n] >target)
            {
                right = mid;
            }else{
                return true;
            }
        }
        // if(matrix[left/n][left%n] == target || matrix[right/n][right%n] == target) return true;
        // else return false;
        return target == matrix[left/n][left%n];
    }
};
```
-二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
```
现有矩阵 matrix 如下：
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
```
```
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int height = matrix.size();
        int width = matrix[0].size();
        int row = 0, col = width - 1;
        while(row<height && col>=0)
        {
            if(matrix[row][col] == target) return true;
            else if(matrix[row][col]>target)
            {
                --col;
            }
            else
            {
                ++row;
            }
        }
        return false;
    }
};
```
##1.15 搜索插入位置
  - `题目要求(search insert postion)`
 - 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

- 你可以假设数组中无重复元素。
  - `测试用例`
```
输入: [1,3,5,6], 5
输出: 2
```
  - `参考代码`
```
        if(nums.empty()) return 0;
        int left = 0,right = nums.size()-1,mid;
        // while(left < right)
        while(left <= right)
        {
            mid = left + (right - left)/2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                // right = mid;
                right = mid-1;
            }else{
                return mid;
            }
        }

// if(target <= nums[left]) return left;
        // else return left + 1;
        return left;
```
## 1.16 寻找峰值
 - `题目要求(162.Find Peak Element)`
- 峰值元素是指其值大于左右相邻值的元素。

- 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

- 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

- 你可以假设 nums[-1] = nums[n] = -∞。

- `测试用例`
```
- 输入: nums = [1,2,1,3,5,6,4]
- 输出: 1 或 5 
- 解释: 你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。
```
 - `参考代码`
```
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int len = nums.size();
        int left = 0,right = len-1,mid;
        while(left <= right)
        {
            mid = left + (right - left)/2;
            if((mid == 0 || nums[mid-1]<nums[mid]) &&(mid == len-1 || nums[mid]>nums[mid+1])) return mid;
            else if(mid > 0 && nums[mid-1] > nums[mid]){
                 right = mid - 1;
            }else if(mid <len-1 && nums[mid] < nums[mid + 1] )
            {
                left = mid + 1;
            }
        }
        return mid;
    }
}; 
```
## 1.17 在排序数组中查找元素的第一个和最后一个位置
```
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
```
```
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        if(nums.empty()) return res;
        //先找第一个位置
        int left = 0,right = nums.size()-1,mid;
        while(left < right)
        {
            mid = (left + right)>>1;
            if(nums[mid]<target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }
        //没找到target,则直接返回
        if(left >= nums.size() ||(nums[left] != target))
            return res;
        res[0] = left;

//直接从left处开始，寻找第二个位置
        right = nums.size()-1;
        while(left <= right)
        {
            mid = (left + right)>>1;
            if(nums[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        } 
        res[1] = right;
        //还可以这么写，注意right起点不一样，最终right需要减一
        // right = nums.size();
        // while(left < right)
        // {
        //     mid = (left + right)>>1;
        //     if(nums[mid] > target)
        //     {
        //         right = mid;
        //     }
        //     else
        //     {
        //         left = mid + 1;
        //     }
        // } 
        // res[1] = right - 1;

return res;
    }
};
```
## 1.18 下一个排列

- 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

- 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

- 必须原地修改，只允许使用额外常数空间。

- 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
```
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
```
- 该算法称为字典序算法:
```
class Solution {
public:
    //字典序算法
    void nextPermutation(vector<int>& nums) {
        if(nums.empty()) return;
        int len = nums.size();
        int pivot = len - 1;
        int nextIdx = len - 1;
        //寻找哨兵位置, 为逆序区域的前一个位置
        for(int i = len-1;i>0;i--)
        {   
            if(nums[i-1] < nums[i])
            {
                pivot = i-1;
                break;
            }
        }
        //全逆序,则直接顺序排列
        if(pivot == len-1)
        {
            //sort(nums.begin(),nums.end(),less<int>());
            reverse(nums.begin(),nums.end()); //逆序效率更高
        }
        else
        {
            //寻找刚好大于哨兵位置的那个数, 并和哨兵交换位置
            nextIdx = pivot + 1;
            for(int i = pivot + 1;i<len;++i)
            {
                if(nums[i] > nums[pivot])
                {
                    nextIdx = nums[nextIdx] < nums[i] ? nextIdx:i;
                }
            }
            int t = nums[pivot];
            nums[pivot] = nums[nextIdx];
            nums[nextIdx] = t;
            //把原来的逆序区域转为顺序
            sort(nums.begin()+pivot+1,nums.end());
        }
    }
};
```
## 1.19 最长连续递增序列
```
给定一个未经排序的整数数组，找到最长且连续的的递增序列。
示例 1:

输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。 
示例 2:

输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
```
```
//可以理解为动态规划
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int result = 1;
        int temp = 1;
        for(int i = 1;i<nums.size();++i)
        {
            if(nums[i]>nums[i-1])
            {
                temp++;
            }
            else
            {
                result = max(result,temp);
                temp = 1;
            }
        }
        //可能最后一个数字依然在递增
        return max(result,temp);
    }
};
```
## 1.20 最长上升子序列
```
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
```
```
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        int length = nums.size();
        //dp[i] 表⽰以 nums[i] 这个数结尾的最⻓递增⼦序列的⻓度,因此至少为1
        vector<int> dp(length+1,1); 
        dp[0] = 1;
        int result = 1;
        for(int i = 1;i<length;++i)
        {
            for(int j = 0;j<i;++j)
            {
                if(nums[i]>nums[j])
                {
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            result = max(result,dp[i]);
        }
        return result;
    }
};
```
## 1.21 数组中的第K个最大元素
```
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
```
```
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return func2(nums,k);
    }
private:
    //方法一，直接全部排序。可以使用优先队列，相当于使用堆排序，这里的是大根堆。(但是这样内存不友好，全放入了堆当中)
    int func1(vector<int> &nums,int k)
    {
        priority_queue<int,vector<int>,less<int>> que;
        for(auto n:nums)
        {
            que.push(n);
        }
        int res = 0;
        while(k--)
        {
            res = que.top();
            que.pop();
        }
        return res;
    }
    //方法二，使用堆，当成TopK问题。求前 k 大,用小根堆,求前 k 小,用大根堆。
    int func2(vector<int>& nums,int k)
    {
        priority_queue<int,vector<int>,greater<int>> pq;
        for(auto n:nums)
        {
            //写法一：思路比较直接，相当于不断利用堆来找最小值
            // if(pq.size()<k)
            // {
            //     pq.push(n);
            // }
            // else
            // {
            //     if(n > pq.top())
            //     {
            //         pq.pop();
            //         pq.push(n);
            //     }
            // }
            //写法二：更简洁
            pq.push(n);
            if(pq.size()>k) pq.pop(); //超出容量就去除堆顶的最小的元素
        }
        int res = pq.top();
        return res;
    }

//方法二：使用快排思想
    int func3(vector<int> &nums,int k)
    {
        int res = 0;
        int index = 0;
        int left = 0,right = nums.size()-1;
        while(left<=right)
        {
            index = partition(nums,left,right);
            if(index == k-1)
            {
                res = nums[index];
                break;
            }
            else if(index<k-1)
            {
                left = index+1;
            }
            else
            {
                right = index-1;
            }
        }
        return res; 
    }

//划分函数,[left,right]
    int partition(vector<int> &nums,int left,int right)
    {
        int pivot = nums[right];
        int tail = left-1;
        for(int i = left;i<right;++i)
        {
            if(nums[i] > pivot)
            {
                swap(nums,++tail,i);
            }
        }
        swap(nums,++tail,right);
        return tail;
    }
    void swap(vector<int> &nums,int i,int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};
```
## 1.22 颜色分类
```
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
```

```
class Solution {
public:
    void sortColors(vector<int>& nums) {
         func2(nums);
    }
private:
    //方法一：两次扫描，计数+修改原数组
    void func1(vector<int>& nums)
    {
        if(nums.size()<=1) return;
        int count[3] = {};
        for(int i = 0;i<nums.size();++i)
        {
            count[nums[i]]++;
        }
        int index = 0;
        for(int i = 0;i<3;++i)
        {
            while(count[i]--)
            {
                nums[index++] = i;
            }
        }
    }
    //方法二：一次扫描
    void func2(vector<int>& nums)
    {
        if(nums.size()<=1) return;
        int left = -1,right = nums.size();
        for(int i = 0;i<right;)
        {
            //0拿到最左边去,i前面的值要么为0，要么为1，不需要再判断i位置，i直接继续移动即可
            if(nums[i] == 0)
            {
                swap(nums,++left,i);
                i++;
            }
            //2拿到最右边去，i不动,因为i位置的值在交换后可能变为0，需要再次判断
            else if(nums[i]==2)
            {
                swap(nums,--right,i);
            }
            //1的话略过
            else
            {
                i++;
            }
        }
    }
    void swap(vector<int>& nums,int i,int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};

```
## 1.23 合并区间
```
给出一个区间的集合，请合并所有重叠的区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
链接：https://leetcode-cn.com/problems/merge-intervals
```
```
bool cmp(vector<int> &a, vector<int> &b)
{
    return a[0] < b[0];
}
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if(intervals.empty()) return res;
        if(intervals.size() == 1) return intervals;

//sort(intervals.begin(),intervals.end(),compare); //cmp写成成员函数要加static，写成全局函数则可加可不加
        sort(intervals.begin(),intervals.end(),cmp);

//start，end用于暂存每个合法的区间
        int start = intervals[0][0],end = intervals[0][1];
        for(int i = 0;i < intervals.size();++i)
        {
            //满足条件则融合到当前区间[start,end]中去
            if(intervals[i][0] <= end)
            {
                if(intervals[i][1] > end)
                {
                    end = intervals[i][1];
                }
            }
            else
            {
                //说明当前的[start,end]是满足条件的独立区间了，则保存区间
                res.push_back(vector<int>({start,end}));
                //更新start和end，当前区间就是新的开始
                start = intervals[i][0];
                end = intervals[i][1];
            }
            //最后一个区间，直接保存
            if(i == intervals.size()-1)
            {
                res.push_back(vector<int>({start,end}));
            }
        }
        return res;
    }
private:
    //如果不加上static，则变成了成员函数，是带有this指针参数的，显然用于排序只能有a，b两个参数，而不能有this参数
    //因此，将compare放到类外也可以，全局函数也不会带有this指针参数
    bool static compare(vector<int> &a, vector<int> &b)
    {
        return a[0] < b[0];
    }
};
```
## 1.24 无重叠区间
```
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:

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

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

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

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

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

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

链接：https://leetcode-cn.com/problems/non-overlapping-intervals
```
本题与前一道题有些类似，不同的是这里对区间结尾进行排序，见注释：
```
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        /* 
        先计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。

在每次选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。那么最后为了得到无重叠的区间，移除的区间个数就是最少的。
        
        而前一道题则是要求合并所有重叠的区间，合并完以后不重叠区间个数是最少的。

按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。
        */
        if(intervals.size() == 0) return 0;
        sort(intervals.begin(),intervals.end(),cmp);
        int start = intervals[0][0];
        int end = intervals[0][1];
        //cnt记录独立区间的个数
        int cnt = 1;
        for(int i = 1;i<intervals.size();++i)
        {
           if (intervals[i][0] < end) {
                continue;
            }
            end = intervals[i][1];
            cnt++;
        }
        return intervals.size() - cnt;
    }
private:
    bool static cmp(vector<int> &a,vector<int> &b)
    {
        return a[1] < b[1];
    }
};
```

## 1.25 最长连续序列
```
给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

链接：https://leetcode-cn.com/problems/longest-consecutive-sequence
```
```
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //要求时间为O(n),就不能排序，这里利用hash表存储包含当前数字n的连续序列的最大长度
        if(nums.empty()) return 0;
        int res = -1;
        unordered_map<int,int> mp;
        for(auto n:nums)
        {
            //不在hash表中才处理
            if(mp.find(n)==mp.end())
            {
                //取出其左右相邻数已有的连续区间长度 left 和 right
                int left = mp.find(n-1) != mp.end()? mp[n-1]:0;
                int right = mp.find(n+1) != mp.end()? mp[n+1]:0;
                int curr_len = 1 + left + right;
                //更新结果和区间长度
                res = max(curr_len,res);
                mp[n] = curr_len;
                mp[n-left] = curr_len;
                mp[n+right] = curr_len;
            }
        }
        return res;
    }
};
```
## 1.26 除了自身以外数组的乘积
```
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
链接：https://leetcode-cn.com/problems/product-of-array-except-self
```
```
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums.size(),1);
        //从左到右
        int temp = 1;
        for(int i = 0;i<nums.size();++i)
        {
            res[i] = temp;
            temp *= nums[i];
        }
        //从右向左
        temp = 1;
        for(int i = nums.size()-1;i>=0;i--)
        {
            //这里一定要乘等
            res[i] *= temp;
            temp *= nums[i];
        }
        return res;
    }
};
```
## 1.27 滑动窗口的最大值
```
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释:

滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
 
链接：https://leetcode-cn.com/problems/sliding-window-maximum
```
```
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty() || k<=0 || nums.size() < k) return vector<int>();
        vector<int> res;
        int totalMax = nums[0];
        int left = 0,right = 0;
        deque<int> maxNumList; //其头部记录最大值
        //防止只有一个元素的情况
        maxNumList.push_back(nums[0]);
        //[left,right]区间
        for(;right < nums.size();++right)
        {   
            //窗口长度等于k时,右移left
            if(right - left + 1 == k)
            {
                res.push_back(maxNumList.front());
                if(nums[left++] == maxNumList.front())
                    maxNumList.pop_front();
            }
            //不为最后一个窗口时, 右移right
            if(right != nums.size()-1)
            {
                int nextNum = nums[right+1];
                //从右边清空掉小于nextNum的值
                while(!maxNumList.empty() && maxNumList.back() < nextNum) 
                    maxNumList.pop_back();
                maxNumList.push_back(nextNum);
            }
        }
        return res;
    }
};
```
## 1.28 寻找重复数
```
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
示例 2:

输入: [3,1,3,4,2]
输出: 3
说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

链接：https://leetcode-cn.com/problems/find-the-duplicate-number
```
```
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if(nums.empty()) return -1;
        int left = 0,right = nums.size()-1,mid;
        while(left < right)
        {
            mid = left + (right - left)/2;
            int cnt = 0;
            for (int num:nums) {
                if (num <= mid) {
                    cnt++;
                }
            }
            // 根据抽屉原理，小于等于 4 的数的个数如果严格大于 4 个，
            // 此时重复元素一定出现在 [1, 4] 区间（left，right指的是值而不是原数组的index）里
            if (cnt > mid) {
                // 重复的元素一定出现在 [left, mid] 区间里
                right = mid;
            } else {
                // if 分析正确了以后，else 搜索的区间就是 if 的反面
                // [mid + 1, right]
                // 注意：此时需要调整中位数的取法为上取整
                left = mid + 1;
            }
        }
        return left;
    }
};
```
## 1.29 前k个高频元素(TOP K问题)
```
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]

提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

链接：https://leetcode-cn.com/problems/top-k-frequent-elements
```
```
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        if(nums.empty() || k <= 0) return vector<int>();
        vector<int> res;
        //TopK问题。求前 k 大,用小根堆,求前 k 小,用大根堆。这里先统计频率
        unordered_map<int,int> freq;
        for(int i = 0;i<nums.size();++i)
        {
            if(freq.find(nums[i]) == freq.end())
            {
                freq[nums[i]] = 0;
            }
            freq[nums[i]]++;
        }
        //因为没有自定义，所以这里的仿函数greater<pair<int,int>会优先按照pair的first来进行排序（当然这里也可以自定义cmp函数）
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        for(auto fr:freq)
        {
            //注意，这里需要将first和second交换一下，使其按照second排序
            pq.push(make_pair(fr.second,fr.first));
            if(pq.size() > k) pq.pop();
        }
        //保存结果
        while(pq.size())
        {
            res.push_back(pq.top().second);
            pq.pop();
        }
        //使频率高的元素出现在前面
        std::reverse(res.begin(),res.end());
        return res;
    }
};
```
## 1.30 回型遍历数组
```
给定一个row行col列的整数数组array，要求从array[0][0]元素开始，按回形从外向内顺时针顺序遍历整个数组。如图所示：
```

```
输入输入的第一行上有两个整数，依次为row和col。
余下有row行，每行包含col个整数，构成一个二维整数数组。
（注：输入的row和col保证0 < row < 100, 0 < col < 100）输出按遍历顺序输出每个整数。每个整数占一行。样例输入

4 4
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
样例输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
```

```
#include <iostream>
#include <string>
#include <memory.h>
#include <stdio.h>
using namespace std;
int a[105][105];
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> a[i][j];
	//[row,col]坐标为可遍历区域的左上角，[m-1,n-1]坐标为可遍历区域的右下角
	int row = 0, col = 0;
	while (row < n || col < m)
	{
		//横着从左到右
		for (int i = row, j = col; j < m && row < n; j++)
			cout << a[i][j] << endl;
		//竖着，从上到下
		row++;
		for (int i = row, j = m-1; i < n && col < m; i++)
			cout << a[i][j] << endl;
		//横着，从右到左
		m--;
		for (int i = n-1, j = m-1; j >= col && row < n; j--)
			cout << a[i][j] << endl;
		//竖着，从下到上
		n--;
		for (int i = n-1, j = col; i >= row && col < m; i--)
			cout << a[i][j] << endl;
		col++;
	}
	system("pause");
	return 0;
}

```
# 2.位运算(Bit Manipulation)
## 2.1 缺失数字
 - `题目要求(268.Missing Number)`
- 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
 - `测试用例`
```
- 输入: [9,6,4,2,3,5,7,0,1]
- 输出: 8
```
- `参考代码`
```
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int x = 0;
        //因为其他数字都是成对出现的，异或后为0，只有缺失的数字，只出现一次，因而最终x即为所求
        for(int i = 0; i<=nums.size();i++)
           x = x^i;
        for(auto n:nums)
           x = x^n;
        return x;
    }
};
```

## 2.2 2的幂
 - `题目要求(231. Power of Two)`
 给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
 - `测试用例`
```
 输入: 16
 输出: true
 解释: 24 = 16
```
 - `参考代码`
```
class Solution {
public:
    bool isPowerOfTwo(int n) {
        //if (n<=0) return false;
        //else if((n & (n-1))==0) return true;
        //else return false;
        //实际上就这一句
        return n>0 && (n & (n-1)) == 0;
    }
};
```
类似的，对于4的幂，有：
```
class Solution {
public:
    bool isPowerOfFour(int num) {
        // if(num <= 0) return false;
        // int t = sqrt(num);
        // if(t*t != num) return false;
        // return (t & t-1) == 0;

if (num < 0 || num & (num-1)){//check(is or not) a power of 2.
        return false;
        }
        return num & 0x55555555;//check 1 on odd bits
    }
};
```
更通用的解法，不需要循环比较，而是直接`数学公式计算(慎用数学计算，数学上正确，程序计算时只会一步一步取约等于，所以不一定精确)`，以4的幂为例，代码如下(不要意外，C++中是有and，or等python风格的关键字的),`但是最近发现log计算是有误差的，所以下面的方法不一定对，比如当num为423时，判断3的幂就会出错`:
```
         return num > 0 and log(num)/log(4) - (int)(log(num)/log(4))  < 1e-14;
        //或者为 return num > 0 && pow(4,(int)(log(num)/log(4))) == num;
```
判断3的幂可以为:
```
        if(n <= 0) return false;
        while(n%3 == 0)
        {
            n/=3;
        }
        return n == 1;
    }
```
## 2.3  位1的个数
 - `题目要求(191. Number of 1 Bits)`
 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
 - `测试用例`
```
- 输入：00000000000000000000000000001011
- 输出：3
- 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
```
 - `参考代码`
```
class Solution {
public:
    int hammingWeight(uint32_t n) {
        //方法1：移位计算即可
        // int ans=0;
        // while(n)
        // {
        //     //除K取余法
        //     //ans+=n%2;
        //     //直接判断二进制最低为的数是不是1
        //     ans+=n&1;
        //     n>>=1;
        // }
        // return ans;
        
        //方法2：技巧性：直接去掉二进制中位置最靠后的1，也类似于移位计算
        int ans=0;
        while(n)
        {
            ans++;
            n&=n-1;
        }
        return ans;
    }
};

```
## 2.4 数组中数字出现的次数
- 面试题56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
```
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
```
```
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        vector<int> res;
        if(nums.empty()) return res;
        //所有数字异或的结果,实际上是待求的两个数字的异或
        int ResultOfExclusiveOR = 0;
        for(auto n:nums) 
            ResultOfExclusiveOR ^= n;
        //ResultOfExclusiveOR之中必定至少包含一个1
        // int offset = 0;
        // while((ResultOfExclusiveOR & 0x01) == 0 && offset < 8*sizeof(int))
        // {
        //      ResultOfExclusiveOR >>= 1;
        //      ++offset;
        // }

//还可以用n&(-n)得到n的二进制为1的最低位
        int flag = ResultOfExclusiveOR &(-ResultOfExclusiveOR);
        //cout<<6<<" "<<int((-6)&6); //结果是2,注意是用补码表示的,6是0110,-6是1010,所以(-6)&6 = 2;
        int n1 = 0,n2 = 0;
        for(auto n:nums)
        {
            //if((n>>offset)&0x01)
            if(n&flag)
                n1^=n;
            else
                n2^=n;
        }
        res.push_back(n1);
        res.push_back(n2);
        return res;
    }
};
```
- 面试题56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
```
示例 1：
输入：nums = [3,4,3,3]
输出：4

示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
```
```
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return func2(nums);
    }
private:
    int func1(vector<int> &nums)
    {
         // 整体思路：将数组所有的数，二进位映射到一个数组里。对应的位，出现1的次数，不能够被3整除，取余后则是结果中的位
        int* helper = new int[32];
        for (int n : nums) {
            for (int j = 31; j >= 0; j--) {
                helper[j] += n & 1;
                n = n >> 1;
            }
        }
        int result = 0;
        for (int i = 31; i >= 0; i--) {
            if (helper[i] % 3 != 0) {
                result += pow(2, 31 - i);
            }
        }
        delete []helper;
        helper = NULL;
        return result;
    }

int func2(vector<int> &nums)
    {
        //解法解析:https://www.cnblogs.com/MyStringIsNotNull/p/12585218.html
        //一次分析32bit的int的各个位在数组的各个数字中出现的次数,变量a表示低位的情况，变量b表示高位的情况
        //理解为三进制,第一次出现a=1,b=0,第二次出现,a=0,b=1,第三次出现,a=0,b=0; 
        //具体代码来说就是,a^num就是在将数据保留到对应的位里面去,而&~b则是在判断是否需要进位
        int a = 0,b = 0;
        for(int num : nums) {
        	a = (a ^ num) & ~b;
        	b = (b ^ num) & ~a;
        }
        return a; //返回b的话,则返回数组中出现两次的数
    }
};
```
## 2.5 比特位计数
```
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]
示例 2:

输入: 5
输出: [0,1,1,2,1,2]
进阶:

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

链接：https://leetcode-cn.com/problems/counting-bits
```
```
class Solution {
public:
    vector<int> countBits(int num) {
        /*
        设dp[i]为i的二进制形式的1的个数，
        i是奇数时，dp[i]=dp[i-1]+1,因为i是在i-1的二进制数上加了个1啊；
        i是偶数时，dp[i]=dp[i/2],因为i就是把i/2往左移（是数左移，末尾补0）得到的，所以1的个数没变
        */
        vector<int> dp(num+1,0);
        for(int i = 1;i<=num;++i)
        {
            //偶数
            if((i&1) == 0)
            {
                dp[i] = dp[i/2];
            }
            else
            {
                dp[i] = dp[i-1] + 1;
            }
        }
        return dp;
    }
};
```
## 2.4 一个数字只出现一次，其他数字出现3次or N次
```
int FindNum(int array[], int nLength, int N)
{
	int bits[32];
	memset(bits,0,32*sizeof(int));
	int i = 0;
	int j = 0;
	for (i = 0; i < nLength; i++)
	{
		for ( j = 0; j < 32; j++)
		{
			int k = (array[i]>>j) & 1; //与1相与的到结果不是0就是1
			bits[j] += k;//记录 bits[] 数组当中 0 到 31 位的 值,bits[0]代表最低位的情况，bits[31]代表最高为的情况
		}
	}
	int res = 0;
	for (j = 0; j < 32;j++)
	{
		if (bits[j]%N != 0)//例如 2 2 2 1 1 1 9 ，那么bits[0]:4 bits[1]:3 bits[2]:0 bits[3]:1 bits[4]:0 ，...
		{
			res += (1<<j);//得到结果
		}
	}
	return res;
}
https://blog.csdn.net/djb100316878/article/details/42192349?utm_source=blogxgwz8
```
# 3. 树(Tree)
## 3.1 二叉树的最大深度
(104. Maximum Depth of Binary Tree)
 - `题目要求`
- 给定一个二叉树，找出其最大深度。

- 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

- 说明: 叶子节点是指没有子节点的节点。
 - `测试用例` 
 略
 - `参考代码`
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int max_dep = 0;
    void travelOfTree(TreeNode* node,int depth)
    {     /*数据自上而下的递归*/
          if(node==NULL)
            return;
          max_dep = depth+1 > max_dep? depth+1:max_dep;
          travelOfTree(node->left,depth+1);
          travelOfTree(node->right,depth+1);
    }

int travel(TreeNode* node)
    {   /*数据自底而上的递归*/
        if(node == NULL) return 0;
        return 1 + max(travel(node->left),travel(node->right));
    }

int maxDepth(TreeNode* root) {
        //法一：
        //travelOfTree(root,0);
        //return max_dep;
        
        //法二(更简单)：
        return travel(root);
    }
};
```
同理，对于二叉树的最小深度(111. Minimum Depth of Binary Tree)递归(自底而上)代码类似:
```
        if(root == NULL) return 0;
        if(root->left == NULL && root->right == NULL) return 1;
        int l = INT_MAX,r = INT_MAX;
        if(root->left) l = minDepth(root->left);
        if(root->right) r = minDepth(root->right);
        return 1 + min(l,r);
```
## 3.2 从中序与后序遍历序列构造二叉树
(106. Construct Binary Tree from Inorder and Postorder Traversal)
 - `题目要求`
- 根据一棵树的中序遍历与后序遍历构造二叉树。

- 注意:
你可以假设树中没有重复的元素。
 - `测试用例`
```
- 中序遍历 inorder = [9,3,15,20,7]
- 后序遍历 postorder = [9,15,7,20,3]
- 返回如下的二叉树：
        3
       / \
      9  20
        /  \
       15   7
```
 - `参考代码`
 ```
 class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return pre_order(0, inorder.size() - 1, 0, inorder.size() - 1, inorder, postorder);
    }

TreeNode *pre_order(int leftin, int rightin, int leftpost, int rightpost, vector<int> &in, vector<int> &post) {
        if (leftin > rightin) return NULL;
        TreeNode *root = new TreeNode(post[rightpost]);
        
        int rootin = leftin;
        while (rootin <= rightin && in[rootin] != post[rightpost]) rootin++;
        int left = rootin - leftin;
        
        root->left = pre_order(leftin, rootin - 1, leftpost, leftpost + left - 1, in, post);
        root->right = pre_order(rootin + 1, rightin, leftpost + left, rightpost - 1, in, post);
        
        return root;
    }
};
 ```
 同理，中序与前序：
 ```
 class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return creator(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }

TreeNode* creator(vector<int>& preorder,vector<int>& inorder,int lef_pre,int rig_pre, int lef_in, int rig_in)
    {
        if(lef_pre > rig_pre || lef_in > rig_in) return NULL;
        
        //构造根节点
        TreeNode* root = new TreeNode(preorder[lef_pre]);
        
        //寻找子节点
        int i = lef_in;
        while(preorder[lef_pre]!=inorder[i]) i++;

//子节点递归
        root->left = creator(preorder,inorder,lef_pre+1,lef_pre+(i-lef_in),lef_in,i-1);
        root->right = creator(preorder,inorder,lef_pre+(i-lef_in+1),rig_pre,i+1,rig_in);

//返回根节点
        return root;
    }
};

```
 ## 3.3 二叉树的层次遍历
 (102. Binary Tree Level Order Traversal)
 
 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
```
例如:
给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]
```
```
class Solution {
public:
    int depth = 0;
    vector<vector<int>> levelOrder(TreeNode* root) {
        //getDepth(root,0);
        //vector<vector<int>> retVec(depth);
        vector<vector<int>> retVec(getHeight(root));
        travel(retVec,root,0);
        return retVec;
    }
    void travel(vector<vector<int>> &retVec,TreeNode* root,int level)
    {
        if(root==NULL) return;
        retVec[level].push_back(root->val);
        travel(retVec,root->left,level+1);
        travel(retVec,root->right,level+1);
    }
    
    //获取二叉树的高度,需要借助全局变量
    void getDepth(TreeNode* root, int dep)
    {
         if(root == NULL) return;
         depth = max(dep+1,depth);
         getDepth(root->left,dep+1);
         getDepth(root->right,dep+1);
    }
    
    //获取二叉树的高度，不需要全局变量
    int getHeight(TreeNode* root)
    {
        if(root==NULL) return 0;
        int lh = getHeight(root->left);
        int rh = getHeight(root->right);
        return lh > rh ? lh+1 : rh+1;
    }
};
```
## 3.4对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
```
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3
```
递归版本：
```
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
         if(root==NULL) return true;
         return symmetricTree(root->left,root->right);   
    }
    bool symmetricTree(TreeNode* ltree,TreeNode* rtree){
         bool ret = true;
         //左右都为空
         if(ltree==NULL && rtree==NULL) ret = true;
         //其中一边为空
         else if((ltree!=NULL && rtree==NULL) || (ltree==NULL && rtree!=NULL)) ret = false;
         //两边均不为空
         else if(ltree!=NULL && rtree!=NULL)
           { 
             //结点值相等
             if(ltree->val==rtree->val) 
             {
                //如果是叶子节点，直接返回
                if(ltree->left==NULL && ltree->right==NULL && rtree->left==NULL && rtree->right == NULL) ret = true;
                //否则需要递归判断
                else ret = symmetricTree(ltree->left,rtree->right) && symmetricTree(ltree->right,rtree->left); 
             }
             else ret = false;
           }
        return ret;
    }
};
```
迭代版本：
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty())
        {
            TreeNode* lhs = q.front();
            q.pop();
            TreeNode* rhs = q.front();
            q.pop();
            
            //其中一个为NULL则直接说明不对称
            if((lhs == NULL && rhs!=NULL) || (lhs!=NULL && rhs == NULL))
            {
                return false;
            }
            //两个均不为NULL
            else if(lhs!=NULL && rhs!=NULL)
            {
                //值不等，也说明不对称
                if(lhs->val != rhs->val)
                {
                    return false;
                }
                //注意入队列的顺序
                q.push(lhs->right);
                q.push(rhs->left);
                q.push(lhs->left);
                q.push(rhs->right);
            }
        }
        return true;
    }
};
```
## 3.5 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
```
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
         bool ret = true;
         if(p==NULL && q==NULL) ret = true;
         else if((p==NULL&&q!=NULL) || (p!=NULL&&q==NULL)) ret = false;
         else{
             bool cond1 = p->val==q->val;
             bool cond2 = isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
             ret = cond1&&cond2;
         }
         return ret;
    }
};
```
## 3.6平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
```
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root==NULL) return true;
        //return balanceTree(root->left,root->right);
        return dfs(root)!=-1;
    }
    
    //方式一：递归暴力比较
    bool balanceTree(TreeNode* p,TreeNode* q)
    {   
        bool ret = true;
        if(p==NULL && q==NULL) ret = true;
        else if(p==NULL&&q!=NULL){
             ret = getHeight(q)<=1;
        }
        else if(p!=NULL&&q==NULL){
             ret = getHeight(p)<=1;
        }
        else{
            int lh = getHeight(p);
            int rh = getHeight(q);
            bool cond1 = abs(lh-rh)<=1;
            ret = cond1&&balanceTree(p->left,p->right)&&balanceTree(q->left,q->right);        
        }
        return ret;
    }

int getHeight(TreeNode* root)
    {
        int ret = 0;
        if(root==NULL) ret = 0;
        else{
           int lh = getHeight(root->left);
           int rh = getHeight(root->right);
           ret = lh>rh?(lh+1):(rh+1);
        }
        return ret;
    }
    
    //方式二：深度优先搜索
    int dfs(TreeNode* root)
    {
        int ret = 0;
        if(root==NULL) ret = 0;
        else{
            int lh = dfs(root->left);
            int rh = dfs(root->right);
            if(lh>=0 && rh>=0)
            {
               int diff = abs(lh-rh);
               ret = diff <= 1? max(lh+1,rh+1):-1;
            }
            else ret = -1;
        }
        return ret;
    }
};
```
## 3.7 翻转二叉树
```
翻转一棵二叉树。

示例：

输入：

4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

4
   /   \
  7     2
 / \   / \
9   6 3   1

链接：https://leetcode-cn.com/problems/invert-binary-tree
```
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL) return NULL;
        //从上至下
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->right);
        invertTree(root->left);
        
        //从下至上
        // TreeNode* temp =  root->left;
        // root->left = invertTree(root->right);
        // root->right = invertTree(temp);
        return root;
    }
};
```

## 3.8 二叉树的前中后序遍历
###前序遍历
```
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ivec;
        //return Func3(root,ivec);
        return Func4(root);
    }
    
    //栈辅助迭代法：参考了别人的做法，将左子节点和右子节点均放入堆栈，更加简单
    vector<int> Func1(TreeNode* root)
    {
      vector<int> ivec;
      stack<TreeNode*> stk;
      if(!root) return ivec;
      stk.push(root);
      while(!stk.empty())
      {
          TreeNode* node = stk.top();
          stk.pop();
          ivec.push_back(node->val);
          if(node->right) stk.push(node->right);
          if(node->left) stk.push(node->left);
      }
      return ivec;
    }
    
    //最开始自己的做法，只将所有右子树结点放入堆栈，不是很常规但是很有用(实际上也很简单)
    vector<int> Func2(TreeNode* root)
    {
        vector<int> ivec;
        stack<TreeNode*> stk;
        if(root==NULL) return ivec;
        while(root)
        {
              ivec.push_back(root->val);
              if(root->left){
                 if(root->right) stk.push(root->right);
                 root = root->left;
              } 
              else if(root->right) root = root->right;
              else{
                  if(stk.empty()) root=NULL;  
                  else{
                      root = stk.top();
                      stk.pop();
                  }
              };
        }
        return ivec;  
    }

//递归方法
    vector<int>& Func3(TreeNode* root,vector<int> &ivec)
    {
        if(root==NULL) return ivec;
        ivec.push_back(root->val);
        if(root->left) ivec = Func3(root->left,ivec);
        if(root->right) ivec = Func3(root->right,ivec); 
        return ivec;
    }

//迭代法：Morris前序遍历，该方法不需要堆栈的辅助，耗时依然是O(n),空间却减少为O(1);
    vector<int> Func4(TreeNode* root)
    { 
        vector<int> ivec;
        if(root == NULL) return ivec;
        TreeNode *curr = root,*pre = root; //当前访问节点以及前驱节点
        while(curr)
        {   
            //直接输出:生死看淡，只要不是第二次回到该节点，则逮到节点就干！这就是前序遍历！
            if(!curr->left)
            {   
                ivec.push_back(curr->val); //第一次访问curr，输出
                curr = curr->right;
            }else{
               //寻找前驱节点
               pre = curr->left;
               while(pre->right!=NULL && pre->right!=curr) pre = pre->right;
               if(pre->right == NULL){
                   //"搭桥"，没有桥说明是第一次访问该节点
                   ivec.push_back(curr->val); 
                   pre->right = curr;
                   curr = curr->left;
               }else{
                   //说明已经“搭桥”了，需要"过河拆桥"，该节点不输出
                   pre->right = NULL;
                   curr = curr->right;             
               }
               /*注意，对应的，中序则是拆桥时再输出，前序是搭桥时输出*/
            }
        }
        return ivec;
    }
};
```
###中序遍历
```
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ivec;
        Func3(root,ivec);
        return ivec;

}
    
    //方法一：递归
    void Func1(TreeNode* root,vector<int>& ivec)
    {
        if(root == NULL) return;
        Func1(root->left,ivec);
        ivec.push_back(root->val);
        Func1(root->right,ivec);
    }
    
    //方法二:使用栈辅助迭代
    void Func2(TreeNode* root,vector<int>& ivec)
    {
         if(root==NULL) return;
         stack<TreeNode*> stk;
        
         //root移动到最左边的子结点(一定为NULL)
         while(root)
         {
            stk.push(root);
            root = root->left;    
         }
         //开始出栈，边出栈边让右结点入栈
         while(!stk.empty())
         {
            root = stk.top();
            stk.pop();
            ivec.push_back(root->val);
            //root存在右结点，则需要拓展
            if(root->right)
            {    
                 root = root->right;
                 while(root)
                 {
                     stk.push(root);
                     root = root->left;
                 }
            }
         }
    }
    
    //方法三：Morris中序迭代法
    void Func3(TreeNode* root,vector<int>& ivec)
    {
        if(root == NULL) return;
        TreeNode *curr = root, *pre = root; //当前结点和前驱结点
        while(curr)
        {
            if(!curr->left){
                //curr左子节点不存在，则可直接输出curr
                ivec.push_back(curr->val);
                curr = curr->right;
            }else{
                //寻找curr的前驱节点
                pre = curr->left;
                while(pre->right!=NULL && pre->right != curr) pre = pre->right;
                //判断是应该“搭桥”还是“拆桥”
                if(pre->right == NULL){
                    pre->right = curr;
                    curr = curr->left;
                }else{
                    ivec.push_back(curr->val);
                    pre->right = NULL;
                    curr = curr->right;
                }
            }
        }
    }
};
```
###后序遍历:
```
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        
        return postOrderMorrisTravelBrief(root);
    }
    
    //方法一：递归，略
    
    //方法二：双栈迭代
    vector<int> postOrderTravel(TreeNode* root)
    {
        vector<int> ivec;
        if(root==NULL) return ivec;
        stack<TreeNode*> node_stk;
        stack<int> status_stk; //代表对应位置的TreeNode的拓展状态
        while(root){
            node_stk.push(root);
            status_stk.push(1); //1代表当前的TreeNode还没有被拓展，可以拓展
            root = root->left;
        }
        while(!node_stk.empty())
        {
           root = node_stk.top();
           node_stk.pop();
           auto root_status = status_stk.top();
           status_stk.pop();
           if(!root_status){
           //二次放进去的，不可再向右拓展，即应该直接使用
             ivec.push_back(root->val);    
           }
           else{
                if(root->right){
                  node_stk.push(root);
                  status_stk.push(0); //代表当前的root是二次放进去的
                  root = root->right;
                  while(root)
                  {
                     node_stk.push(root);
                     status_stk.push(1); 
                     root = root->left;
                  }
               }
               else ivec.push_back(root->val);
           }
        }
        return ivec;
    }
    //方法三：单栈迭代,每次暂存前一个节点，与当前节点比较后，得到当前节点是否应该拓展
    vector<int> postorderSingleStackTravel(TreeNode* root)
    {
       vector<int> ivec;
       if(root == NULL) return ivec;
       stack<TreeNode*> stk;
       TreeNode *curr = root,*prev = NULL; //当前节点和前一个节点
       while(curr){  //栈初始化，curr最后为NULL，这是与下面的不同点
           stk.push(curr);
           curr = curr->left;
       }
       while(!stk.empty())
       {
            curr = stk.top();
            stk.pop();
            if(curr->right == NULL) ivec.push_back(curr->val);
            else
            {//当前节点存在右节点，如果是第一次则需要拓展，第二次则不再需要
                if(prev == curr->right)//不需要拓展，直接输出
                ivec.push_back(curr->val);
                else//可能需要拓展,拓展前，需要将curr放回stk
                { 
                      stk.push(curr);
                      curr = curr->right;
                      stk.push(curr);
                      while(curr->left){ //找到最左边的节点，curr最后不为NULL，不然prev没法记录
                          curr = curr->left;
                          stk.push(curr);
                         }  
                }
            }
            //记录前一个节点
            prev = curr;
       }
       return ivec;
    }
    //方法四：Morris后序遍历
    vector<int> postOrderMorrisTravel(TreeNode* root)
    {
        vector<int> ivec;
        if(root == NULL) return ivec;
        TreeNode *curr = root,*prev = NULL;
        while(curr)
        {
            if(curr->left == NULL){
               curr = curr->right;
            }else{  //寻找前驱节点
               prev = curr->left;
               while(prev->right!=NULL && prev->right!=curr) prev = prev->right;
               //判断前驱节点，是应该“搭桥”还是“拆桥”
               if(prev->right == NULL)
               {
                    prev->right = curr; //“搭桥”
                    curr = curr->left;
               }else{
                    prev->right = NULL; //"拆桥"
                    //逆序输出curr的所有左子树的最右边界
                    rerverseRightEdge(curr->left,ivec);          
                    //工作指针移动
                    curr = curr->right;
               }
            }
        }
        rerverseRightEdge(root,ivec);
    
        return ivec;
    }
    vector<int>& rerverseRightEdge(TreeNode* root,vector<int>& ivec)
    {
        if(root == NULL) return ivec;
        TreeNode *prev = root,*curr = root->right,*post = NULL;
        //所有右子节点反向
        if(curr == NULL) {
            ivec.push_back(root->val);
            return ivec;
        }
        prev->right = NULL;
        post = curr->right;
        while(curr)
        {//最终prev保存最后一个节点，curr和post为NULL
             curr->right = prev;    
             //移动curr
             prev = curr;
             curr = post;
             if(post) post = post->right;
        }
        //逆序输出,并还原
        curr = prev;
        post = NULL;
        prev = prev->right;
        while(curr)
        {
            ivec.push_back(curr->val);
            //恢复
            curr->right = post;
            //移动curr
            post = curr;
            curr = prev;
            if(prev) prev = prev->right;
        }
        return ivec;
    }
    //方法五：精简版本的Morris后续遍历：一般的Morris后续遍历需要一个逆序打印的函数，因为多个地方用到了该函数
    //考虑增加一个超根节点，则不必将逆序打印写成函数，更精简
    vector<int> postOrderMorrisTravelBrief(TreeNode* root)
    {
        vector<int> ivec;
        if(root == NULL) return ivec;
        //超根节点
        TreeNode* sudo_root = new TreeNode(0);
        sudo_root->left = root;
        TreeNode *curr = sudo_root,*prev = NULL;
        while(curr)
        {
            if(curr->left == NULL){
               curr = curr->right;
            }else{  //寻找前驱节点
               prev = curr->left;
               while(prev->right!=NULL && prev->right!=curr) prev = prev->right;
               //判断前驱节点，是应该“搭桥”还是“拆桥”
               if(prev->right == NULL)
               {
                    prev->right = curr; //“搭桥”
                    curr = curr->left;
               }else{
                    prev->right = NULL; //"拆桥"
                    //逆序输出curr的所有左子树的最右边界
                    rerverseRightEdge(curr->left,ivec);          
                    //工作指针移动
                    curr = curr->right;
               }
            }
        }
        //还原二叉树
        sudo_root->left = NULL;
        delete sudo_root;
        return ivec;
    }
};
```
## 3.9 填充每个节点的下一个右侧指针
 - `题目要求(116. Populating Next Right Pointers in Each Node):`
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
```
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
```
- 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

- 初始状态下，所有 next 指针都被设置为 NULL。

- `测试样例`

- `参考代码`
```
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        // if(root){
        //     Func1(root,root->left,0);
        //     Func1(root,root->right,1);
        // }
        //Func2(root);
        Func3(root);
        return root;
    }
    
    //方法一：考虑递归方法
    void Func1(Node* pre,Node* root,int lr)
    {   
        if(root==NULL) return; 
        if(lr==0){
              root->next = pre->right;
              
        }else{
               if(pre->next) root->next = pre->next->left;
               else root->next=NULL;
        }
        Func1(root,root->left,0); //这里，有root，便可以求出后面两个参数，所以写法有点冗余
        Func1(root,root->right,1);  
    }

//方法二：另一个递归版本，更简洁
    void Func2(Node* root)
    {
        if(root==NULL) return;
        else{
            if(root->left) root->left->next = root->right;
            if(root->right && root->next) root->right->next = root->next->left;
        }
        Func2(root->left);
        Func2(root->right);
    }
    //方法三:迭代版本，只占用常量级空间，则需要利用next指针
    void Func3(Node* root)
    {
        if(root==NULL) return;
        Node* p = root;
        Node* next_layer = p->left;
        while(next_layer)
        {
           while(p){
              if(p->left) p->left->next = p->right;
              if(p->right && p->next) p->right->next = p->next->left;
              //向右平移
              p = p->next;
           }
           //左下移动
           p = next_layer;
           next_layer = next_layer->left;
        }
    }

};

```
当不是完美二叉树时，则代码更具普适性，参考代码为:
```
class Solution {
public:
    Node* connect(Node* root) {
        func2(root);
        return root;
    }
    
    //递归
    void func1(Node* root)
    {
        if(root==NULL) return;
        Node*p =root;
        if(root->left){
           if(root->right) root->left->next = root->right;
           else{
               p = root->next;
               while(p){
                    if(p->left){ root->left->next = p->left;break;}
                    else if(p->right) {root->left->next = p->right;break;}
                    else p = p->next;
               }
               //if(p==NULL) root->left->next = NULL;
           }
        }
        if(root->right){
                 p = root->next;
                 while(p){
                     if(p->left){ root->right->next = p->left;break;}
                     else if(p->right){root->right->next = p->right;break;}
                     else {p = p->next;};
                 }
              
        } 
        //采用递归时，必须先右子树，再左子树，因为左边依赖于右边，右边的所有next指针没有处理完，先处理左边可能会出错
        //否则类似于[2,1,3,0,7,9,1,2,null,1,0,null,null,8,8,null,null,null,null,7]这种通不过
        func1(root->right);
        func1(root->left);
    }

void func2(Node* root)
    {
        if(root==NULL) return;
        Node* q = root,*p = root;
        Node* next_layer;
        if(root->left) next_layer = root->left;
        else if(root->right) next_layer = root->right;
        else next_layer=NULL;
        while(next_layer){
            while(q){
                //迭代方式，先处理左边或者右边都可以
                if(q->left){
                    if(q->right) q->left->next = q->right;
                    else{
                        p = q->next;
                        while(p){
                            if(p->left){q->left->next = p->left;break;}
                            else if(p->right){q->left->next = p->right;break;}
                            else p = p->next;
                        }
                    }
                }

if(q->right){
                    p = q->next;
                    while(p){
                        if(p->left){q->right->next = p->left;break;}
                        else if(p->right){q->right->next = p->right;break;}
                        else p = p->next;
                    }
                }
                q = q->next;
            }
            //切换到下一层
            q = next_layer;
            while(next_layer){
                if(next_layer->left){ next_layer = next_layer->left;break;}
                else if(next_layer->right) {next_layer = next_layer->right;break;}
                else next_layer = next_layer->next;
            }
        }    
       
    }
};

```
## 3.10 有序链表转换二叉搜索树
(109. convert sorted list to binary search tree)

- 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

- 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
- `参考代码`
```
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
       return recursiveFunc(head,NULL);
    }
    TreeNode* recursiveFunc(ListNode* head,ListNode* tail)
    {
        if(head == tail) return NULL;
        ListNode *slow = head,*fast = head;
        while(fast!=tail && fast->next!=tail)
        {
            slow = slow->next;
            fast = fast->next->next;
        }   
        TreeNode* node = new TreeNode(slow->val);
        node->left = recursiveFunc(head,slow);
        node->right = recursiveFunc(slow->next,tail);
        return node;
    }
};
```
- 如果只是有序数组而不是有序链表，那么更加简单了：
```
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return dfs(nums,0,nums.size());
    }
    //递归，这里是左闭右开区间：[left,right)
    TreeNode* dfs(vector<int>& nums,int left,int right)
    {
        if(left==right) return NULL;
        int mid = left + (right - left)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = dfs(nums,left,mid);
        root->right = dfs(nums,mid+1,right);
        return root;
    }
};

```
## 3.11 二叉树展开为链表
(Flatten Binary Tree to Linked List)
给定一个二叉树，原地将其展开为一个链表(全部节点左子设为NULL,通过右子节点连接):
```
class Solution {
public:
    void flatten(TreeNode* root) {
         DFS(root);
    }

TreeNode* dfs(TreeNode* root)
    {
         if(root==NULL || (root->left==NULL && root->right==NULL)) return root;
         TreeNode* temp = root->right;//暂存原来的右子节点
         TreeNode* ret = NULL; //按照前序搜索得到的最后一个节点
         //有左子节点才处理,否则直接将右子树temp捋直
         if(root->left){
           root->right = root->left;
           root->left = NULL;
           //按照前序，返回左子树的最后一个节点  
           ret = dfs(root->right);
           //原来的右子节点存在，才接上
           if(temp) {
              ret->left = NULL;
              ret->right = temp;
           }
         }
         //无论是否将temp接上，均需要将右子树temp捋直
         if(temp) ret = dfs(temp);
         return ret;
    }
    //换一下写法，但是好像也没有更简洁？？？
    TreeNode* DFS(TreeNode* root)
    {
         if(root==NULL || (root->left==NULL && root->right==NULL)) return root;
         TreeNode* temp = root->right;//暂存原来的右子节点
         TreeNode* ret = NULL; //按照前序搜索得到的最后一个节点

//有左子节点才处理,否则直接
         if(root->left){
           root->right = root->left;
           root->left = NULL;
           //按照前序，返回左子树的最后一个节点  
           ret = DFS(root->right);
         }
         //原来的右子节点存在
         if(temp) {
             if(ret){
               ret->left = NULL;
               ret->right = temp;
             } 
             ret = DFS(temp);
         };
         return ret;
    }
};

```
## 3.12 验证二叉搜索树
(98.validate binary search tree)
  - `题目要求`
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
```
class Solution {
public:
    bool isValidBST(TreeNode* root){

//return valid(root,LONG_MIN,LONG_MAX);

return validDFS(root,NULL,NULL);
    }
    //错误代码，该代码无法判断爷孙的合法性,因为递归的时候，没有向下传递取值范围信息
    bool dfs(TreeNode* root){
        if(root == NULL) return true; 
        if(root->left == NULL && root->right == NULL) return true; 
        
        bool ret1 = true,ret2= true;         
        if(root->left) ret1 = root->left->val < root->val; 
        if(root->right) ret2 = root->val < root->right->val;
        
        return ret1 && ret2 && isValidBST(root->left) && isValidBST(root->right);
    }
    //正确代码,但是没法处理[-2147483648,null,2147483647]，因为整型溢出,将INT_MIN改成LONG_MIN都不行
    bool valid(TreeNode* root,int minval,int maxval){
        if(!root){return true;}
        //if(root->left == NULL && root->right == NULL) return true; 
        if(root->val<= minval || root->val >= maxval) return false;
        return valid(root->left,minval,root->val) && valid(root->right,root->val,maxval);
    }
    //正确代码，可以处理溢出的案例
    bool validDFS(TreeNode* root, TreeNode* minNode,TreeNode* maxNode)
    {
        if(!root){return true;}
        if((minNode && minNode->val>=root->val)||(maxNode && maxNode->val <= root->val)) return false;
        return validDFS(root->left,minNode,root) && validDFS(root->right,root,maxNode);
    }
};
```
## 3.13 恢复二叉搜索树
 - (99. Recover Binary Search Tree)二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        inorderMorrisTraversalBrief(root);
    }
    //使用Morris中序遍历，其空间复杂度刚好为O(1)，满足要求
    void inorderMorrisTraversal(TreeNode* root)
    {
        if(root == NULL) return;
        TreeNode *curr = root,*prev = NULL,*last = NULL,*lastpre = NULL; //当前工作节点，前驱节点，以及上一次,上上次的工作节点
        TreeNode *mis1 = NULL,*mis2 = NULL; //记录两个错误的节点，mis1为第一次“凸起”的地方，mis2为最后一次“凹陷”的地方
        while(curr)
        {
            if(!curr->left)
            {
                //出现了可以判断的curr，则判断last是否异常
                judge(lastpre,last,curr,mis1,mis2);
                
                //last,lastpre指针移动,这里不知道下一次可以参与判断的curr
                lastpre = last;
                last = curr;
                
                //移动curr指针
                curr = curr->right;
            } 
            else
            {
                prev = curr->left;
                while(prev->right!=NULL && prev->right!=curr) prev = prev->right;
                if(prev->right == NULL)
                {   //搭桥 以及移动curr指针
                    prev->right = curr;
                    curr = curr->left;}
                else
                {
                    //判断是否异常
                    judge(lastpre,last,curr,mis1,mis2);

//移动判断指针last,lastre
                    lastpre = last;
                    last = curr;

//"拆桥" 以及移动curr指针(这里移动过后的curr不能用来判断)
                    prev->right = NULL;
                    curr = curr->right;     
              }
            }
        }
        
        //最后当curr为NULL时，即last为最后一个节点时，也需要判断一次
        judge(lastpre,last,curr,mis1,mis2);
        
        //交换mis1位置和mis2位置的值，不改变二叉树结构
        int t;
        t = mis1->val;
        mis1->val = mis2->val;
        mis2->val = t;
    }

void judge(TreeNode* lastpre,TreeNode* last,TreeNode* curr,TreeNode* &mis1,TreeNode* &mis2) //对指针变量进行引用，这种不是很常用
    {
        //判断是否异常
        if(lastpre == NULL){//lastre为NULL时,curr不可能为NULL，否则二叉树只有一个节点
            if(last == NULL) return;//刚开始的时候会出现lastpre和last均为NULL的情况
            
            //对于mis1位置的寻找，只有第一次出现的“凸起”位置才是满足要求的，比如[1,5,3,4,2,6],4也是突起的，但不符合题意
            if(mis1 == NULL && last->val > curr->val){ mis1 = last;}
        }  
        else if(curr==NULL){ //同上，lastpre此时不可能为NULL             
            if(last->val < lastpre->val ) {mis2 = last;}
        }
        else{ //lastpre，last，curr均不为NULL
            //只寻找第一个“凸起”位置
            if(mis1 == NULL && lastpre->val < last->val && last->val > curr->val){mis1 = last;} 
            //寻找最后一个满足条件的“凹处”
            if(lastpre->val > last->val && last->val <curr->val) {mis2 = last;}
        }
    }

//大概看了一下别人的代码，发现前面自己写的稍微有些麻烦了，其实不需要三个指针，两个即可,修改后的精简版代码：
    void inorderMorrisTraversalBrief(TreeNode* root)
    {
        if(root == NULL) return;
        TreeNode* curr = root, *prev = NULL, *before = NULL; //工作指针，前驱节点，前一个输出节点
        TreeNode *p1 = NULL,*p2 = NULL; //记录两个被错误地交换的节点
        while(curr)
        {
            //如果存在左孩子
            if(curr->left)
            {
               prev = curr->left;
               while(prev->right!=NULL && prev->right!=curr) prev = prev->right;
               if(prev->right == NULL)
               {
                   prev->right = curr;
                   curr = curr->left;
               }else{
                   //----判断是否异常
                   if(before!=NULL && before->val > curr->val)
                   {
                        if(p1 == NULL){
                           p1 = before;
                           p2 = curr; //因为有可能p1,p2是挨着的
                        }
                        else{ p2 = curr;}
                   }
                   //移动before判断指针
                   before = curr;
                   
                   //移动输出指针
                   prev->right = NULL;
                   curr = curr->right;
               }
            }
            else{//不存在左孩子
                //------判断是否异常
                if(before!=NULL && before->val > curr->val)
                {
                    if(p1 == NULL){
                        p1 = before;
                        p2 = curr;  //因为有可能p1,p2是挨着的
                    }
                    else{ p2 = curr;}  //这里就只更新p2了
                }
                //移动before判断指针
                before = curr;

//移动curr指针
                curr = curr->right;
            }
        }
        //不改变结构，只交换节点值
        int temp = p1->val;
        p1->val = p2->val;
        p2->val = temp;
    }

};
```
## 3.14 二叉树的所有路径
 - `题目要求`
- 给定一个二叉树，返回所有从根节点到叶子节点的路径。
- 说明: 叶子节点是指没有子节点的节点。
 - `测试样例`
```
- 输入:

1
 /   \
2     3
 \
  5

- 输出: ["1->2->5", "1->3"]

- 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
```
 - `参考代码`
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        return allPaths(root);
    }
    
    //方法一：拷贝（或者引用）temp加递归
    vector<string> allPaths(TreeNode* root) {
        vector<string> allpath;
        if(root == NULL) return allpath;
        if(root->left == NULL && root->right == NULL){
            allpath.push_back(to_string(root->val));
            return allpath;
        }
        //因为第一个数组前面没有箭头，所以这样单独处理
        string temp = to_string(root->val);
        dfs(allpath,root->left,temp);
        dfs(allpath,root->right,temp);
        return allpath;
    }   
   //深度搜索：递归，从上到下
   void dfs(vector<string> &allpath,TreeNode *root,string &temp)
   {
       if(root == NULL) return;
       string curr ="->"+to_string(root->val);
       int len = curr.size();
       temp+=curr;
       if(root->left == NULL && root->right == NULL) {allpath.push_back(temp);}
       dfs(allpath,root->left,temp);
       dfs(allpath,root->right,temp);
       //如果temp采用普通的拷贝传参，则不需要这句，但是那样内存消耗会很大
       temp.erase(temp.end()-len,temp.end());
   }

//方法二：迭代方式，使用栈辅助，前序遍历即可

};

```
## 3.15 求根到叶子节点数字之和
- (129. Sum Root to Leaf Numbers) 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
```
- 例如，从根到叶子节点路径 1->2->3 代表数字 123。
```
- 计算从根到叶子节点生成的所有数字之和。

- 说明: 叶子节点是指没有子节点的节点。
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        vector<int> numbers;
        int sum = 0;
        dfs(root,numbers,sum);
        return sum;
    } 
   void dfs(TreeNode* root,vector<int> &numbers,int &sum){
        if(root == NULL) return;
        numbers.push_back(root->val);
        if(root->left == NULL && root->right == NULL){
             int num = 0;
             for(auto n:numbers){
                 num = num*10 + n;
             }
             sum+=num;
             //这里不能return，否则最后一个val无法pop_back
        }
        dfs(root->left,numbers,sum);
        dfs(root->right,numbers,sum);
        numbers.pop_back();
   }
};
```
## 3.16 二叉树的最大路径和
(124. Binary Tree Maximum Path Sum)
 - `题目要求`
- 给定一个非空二叉树,结点值可能为负数，返回其最大路径和。

- 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
 - `测试样例`
```
输入: [1,2,3]

1
      / \
     2   3
输出: 6
```
 - `参考代码`：
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        //root为非空二叉树
        int ret = root->val;
        getMaxPathSum(root,ret);
        return ret;
    }

int getMaxPathSum(TreeNode* root,int &ret)
   {
        /**
        对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
        1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
        2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
        **/
       if(root == NULL) return 0;
       //因为测试样例包含负值，出现负值时用0代替，表示该路径不要
       int left = max(0,getMaxPathSum(root->left,ret));
       int right = max(0,getMaxPathSum(root->right,ret));
       
       //判断ret
       ret = max(ret,root->val+right+left); //这里就可以看出为什么要限制left，right非负
       return max(left,right) + root->val;
   } 
};
```
## 3.17 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。
```
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
         if(root==NULL) return false;
         if(root->left==NULL && root->right==NULL) return root->val == sum;
         return hasPathSum(root->left,sum-root->val) || hasPathSum(root->right,sum-root->val);
    }
};
```
如果需要返回路径的话，则为：
```
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> allPath;
        vector<int> currPath;
        findPathRecall(allPath,currPath,root,sum);
        return allPath;
    }
    
    //法一：递归，+currPath拷贝，数据从上向下传递
    void findPath(vector<vector<int>> &allPath,vector<int> currPath,TreeNode* root,int sum)
    {
       if(root == NULL) return;
       currPath.push_back(root->val);
       if(root->left==NULL && root->right==NULL){
           if(sum == root->val) {
               allPath.push_back(currPath);
           }
           //return;//这里是否return均可
       }
       findPath(allPath,currPath,root->left,sum-root->val);
       findPath(allPath,currPath,root->right,sum-root->val);
    }
    //法二：递归回溯，+currPath引用（占用空间更少，效率更高），数据从上向下传递
    void findPathRecall(vector<vector<int>> &allPath,vector<int> &currPath,TreeNode* root,int sum)
    {
       if(root == NULL) return;
       currPath.push_back(root->val);
       if(root->left==NULL && root->right==NULL){
           if(sum == root->val) {
               allPath.push_back(currPath);
           }
           //这里不能return;因为一旦return，currPath的最后一个值则不能被pop掉
           //因此可以采用下面的代码，这样少做递归，效率更高
           currPath.pop_back();
           return;
       }
       findPathRecall(allPath,currPath,root->left,sum-root->val);
       findPathRecall(allPath,currPath,root->right,sum-root->val);
       //currPath还原
       currPath.pop_back();
    }
};
```
## 3.18 路径总和II
```
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]
https://leetcode-cn.com/problems/path-sum-ii
```
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> allPath;
        vector<int> currPath;
        findPathRecall(allPath,currPath,root,sum);
        return allPath;
    }
    
    //法一：递归，+currPath拷贝，数据从上向下传递
    void findPath(vector<vector<int>> &allPath,vector<int> currPath,TreeNode* root,int sum)
    {
       if(root == NULL) return;
       currPath.push_back(root->val);
       if(root->left==NULL && root->right==NULL){
           if(sum == root->val) {
               allPath.push_back(currPath);
           }
           //return;//这里是否return均可
       }
       findPath(allPath,currPath,root->left,sum-root->val);
       findPath(allPath,currPath,root->right,sum-root->val);
    }
    //法二：递归回溯，+currPath引用（占用空间更少，效率更高），数据从上向下传递
    void findPathRecall(vector<vector<int>> &allPath,vector<int> &currPath,TreeNode* root,int sum)
    {
       if(root == NULL) return;
       currPath.push_back(root->val);
       if(root->left==NULL && root->right==NULL){
           if(sum == root->val) {
               allPath.push_back(currPath);
           }
           //这里不能return;因为一旦return，currPath的最后一个值则不能被pop掉
           //因此可以采用下面的代码，这样少做递归，效率更高
           currPath.pop_back();
           return;
       }
       findPathRecall(allPath,currPath,root->left,sum-root->val);
       findPathRecall(allPath,currPath,root->right,sum-root->val);
       //currPath还原
       currPath.pop_back();
    }
};
```
## 3.19 路径总和III
```
给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

实例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

https://leetcode-cn.com/problems/path-sum-iii
```
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //双重递归，基本思想:将每个节点分别看作根节点和非根节点
    int pathSumCore(TreeNode* root, int sum, int curSum) {
	   if (!root) {
		   return 0;
	   }
	   curSum += root->val;
	   return (curSum==sum)+pathSumCore(root->left, sum, curSum)+ pathSumCore(root->right, sum, curSum);
   }
   int pathSum(TreeNode* root, int sum) {
	   if (!root) {
		   return 0;
	   }
	   return pathSumCore(root,sum,0) + pathSum(root->left,sum)+ pathSum(root->right, sum);
   }
};
```
## 3.20 二叉树的最近公共祖先
```
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
```
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        /*lowestCommonAncestor函数，在对应的root中，按照下面的方式理解：
        如果 p 和 q 都存在，则返回它们的公共祖先；
        如果只存在一个，则返回存在的一个；
        如果 p 和 q 都不存在，则返回NULL
        */
        /*
        具体思路：
            （1） 如果当前结点 root 等于 NULL，则直接返回 NULL
            （2） 如果 root 等于 p或者 q ，那这棵树一定返回 p 或者 q
            （3） 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 left 和 right表示
            （4） 此时若left为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left
            （5） 如果 left 和 right 都非空，因为只给了 p 和 q两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先
            （6） 如果 left 和 right 都为空，则返回空（其实已经包含在前面的情况中了）
        */
        if(root == NULL) return NULL;
        if(root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left == NULL) return right;
        if(right == NULL) return left;
        if(left && right) return root;
        return NULL;
    }
};
```

## 3.21 合并二叉树
```
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7
注意: 合并必须从两个树的根节点开始。
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
```
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1 == NULL) return t2;
        if(t2 == NULL) return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left,t2->left);
        t1->right = mergeTrees(t1->right,t2->right);
        return t1;
    }
};
```
## 3.22 二叉树的序列化和反序列化
```
请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"
注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
```
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string serialization = "[";
        if(root == NULL) return serialization + "]";
        queue<TreeNode*> Qtree;
        Qtree.push(root);
        TreeNode* p = root;
        int levelWidth = 1;
        bool hasNode = true;
        while(!Qtree.empty())
        {
            p = Qtree.front();
            Qtree.pop();
            if(p!=NULL)
            {      
                if(p!=root) serialization.append(","+to_string(p->val));
                else serialization.append(to_string(p->val));

Qtree.push(p->left);
                Qtree.push(p->right);
            }
            else serialization+=(",null");
        }
        serialization.append("]");
        return serialization;
    }

// Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty() || data == "[]") return NULL;
        vector<TreeNode*> nodeVec;
        int negative = 1;
        int levelLen = 1;
        //由序列解析所有的树结点
        for(int i = 0;i<data.size();++i)
        {
            //忽略该字符
            if(data[i] == '[' || data[i] == ',' || data[i] == ']' || data[i] == '+'){continue;}
            if(data[i] == '-') { negative = -negative;continue;}

if(data[i]>='0' && data[i]<='9')
            {
                int val = data[i]-'0';
                while(i<data.size()-1 && data[i+1]>='0' && data[i+1]<='9')
                {
                    val = val*10 + data[i+1] - '0';
                    ++i;
                }
                TreeNode *tnode = new TreeNode(val*negative);
                negative = 1;
                nodeVec.push_back(tnode);
            }
            else if(data[i] == 'n')
            {
                if(data[i+1] == 'u' && data[i+2] == 'l' && data[i+3] == 'l')
                {
                    i+=3;
                    nodeVec.push_back(NULL);
                }
            }
        } 
        //连接所有结点
        queue<TreeNode*> que;
        int index = 0;
        que.push(nodeVec[index++]);
        while(!que.empty() && index < nodeVec.size())
        {
            TreeNode* curr = que.front();
            que.pop();

curr->left = nodeVec[index++];
            curr->right = nodeVec[index++];

if(curr->left) que.push(curr->left);
            if(curr->right) que.push(curr->right);
        }
        return nodeVec[0];
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
```
## 3.23 根据数组创建二叉树
比如输入的数组为elem = {2,NULL,3,NULL,NULL,4,5};
```
//二叉树的节点定义
class TreeNode {
     public:
         int val;
         TreeNode *left, *right;
         TreeNode(int val) {
             this->val = val;
             this->left = this->right = NULL;
         }
};

TreeNode *createBinaryTreeByLevel(vector<int> elem, int curindex)
{
     if (curindex > elem.size() - 1 || elem[curindex] == NULL)
         return NULL;
     TreeNode* node = new TreeNode(elem[curindex]);
     //left hand side
     node->left = createBinaryTreeByLevel(elem, 2 * curindex + 1);
     //right hand side
     node->right = createBinaryTreeByLevel(elem, 2 * curindex + 2);
     return node;
}

```

lee-romantic 's Blog

导航

最近发表

友情链接