二分法

BM21 旋转数组的最小数字

#include <climits>
class Solution {
public:int minNumberInRotateArray(vector<int>& nums) {if(nums.size() <= 0) return 0;int left=0, right=nums.size()-1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] > nums[right])//右边是降序 最小的数字在mid右边left = mid+1;else if(nums[mid] < nums[right])//右边是升序 最小数字要么是mid（奇数个数字） 要么在mid左边（偶数个）right = mid;else right--;//无法判断，一个一个试}return nums[left];}
};

BM22 比较版本号

看解答写的，两个指针依次遍历两个字符串，分为字符处理与比较两部分：
首先把小数点之前的字符转化为数字，跳过当前小数点，处理两个字符串；
然后得到的数字。

class Solution {
public:int compare(string version1, string version2) {int res = 0;int v1 = 0, v2 = 0;long long num1 = 0, num2 = 0;while(v1<version1.size() || v2<version2.size()){num1 = 0;//截取最近一个小数点之前的数字while(v1 < version1.size() && version1[v1] != '.'){num1 = num1 * 10 + version1[v1] - '0';v1++;}//跳过该小数点v1++;//相同的处理num2 = 0;while(v2 < version2.size() && version2[v2] != '.'){num2 = num2 * 10 + version2[v2] - '0';v2++;}v2++;//比较数字if(num1 > num2) return 1;if(num1 < num2) return -1;}return 0;}
};

一开始自己想的就是这种办法，使用流输入istringstream来分割：

• 使用字符串流输入，按照点将两个原始字符串分割，使每个修订号的数字单独呈现在数组中；
• 遍历数组，每次各自取出一个数字比较，较短的版本号没有可取的数字了，就直接取0；
• 遍历取出的数字字符串，将其转换成数字，比较数字大小，根据大小关系返回值。如果全部比较完都无法比较出大小关系，则返回0。

这种解法要学习的一个是流输入的使用，一个是较短版本号的处理

#include <sstream>
class Solution {public:int compare(string version1, string version2) {//使用流输入istringstreamvector<string> num1;vector<string> num2;istringstream ss1(version1);istringstream ss2(version2);string temp;//流输入分割while(getline(ss1, temp, '.'))num1.push_back(temp);while(getline(ss2, temp,'.'))num2.push_back(temp);//字符串转数字 比较for(int i=0; i<num1.size() || i<num2.size(); i++){//较短的版本号取0 这个处理很好string s1 = i < num1.size() ? num1[i] : "0";string s2 = i < num2.size() ? num2[i] : "0";long long num1 = 0, num2 = 0;for(int j = 0; j<s1.size(); j++)num1 = num1 * 10 + s1[j] - '0';for(int j=0; j<s2.size(); j++)num2 = num2 * 10 + s2[j] - '0';//比较数字if(num1 > num2) return 1;if(num1 < num2) return -1;}return 0;}
};

力扣-旋转数组的查找

二分里边再次二分

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size()-1;int mid = 0, index = 0;while(left <= right){mid = left + (right - left) / 2;if(nums[mid] == target) return mid;//先看mid 在左边还是右边 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段 if(nums[left] <= nums[mid])//mid在左边{//再看target在mid的左边还是右边  再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hiif(target >= nums[left] && target < nums[mid])//在左边 后半段不能取等号{right = mid-1;}else left = mid+1;}else//nums[left] > nums[mid]{if(target > nums[mid] && target <= nums[right])//在mid右边left = mid+1;else right = mid-1;}}return -1;}
};

力扣-两个非空链表逆序相加

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//if(l1->val==0 && l2->val==0) return l1;ListNode* dummyhead = new ListNode(0);ListNode* cur = dummyhead;int flag = 0;int val1 = 0, val2 = 0, sum = 0;while(l1!=nullptr || l2!=nullptr){//数字处理部分val1 = (l1 == nullptr) ? 0 : l1->val;val2 = (l2 == nullptr) ? 0 : l2->val;sum = val1 + val2 + flag;flag = sum / 10;//进位不加判断 直接取整数 大于等于10取1，否则取0sum  = sum % 10;//取余数//cout << "l1:" << val1 << "  l2:" << val2 << endl;//cout << "sum:" << sum << "  flag:" << flag << endl;cur->next = new ListNode(sum);//指向新结点，连接链表//节点更新cur = cur->next;if(l1 != nullptr) l1 = l1->next;if(l2 != nullptr) l2 = l2->next;}//如果还有进位的话要加上 最高位 如测试用例3if(flag == 1) cur->next = new ListNode(flag);return dummyhead->next;}
};

二叉树

BM23 二叉树的前序遍历

描述：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

• 递归法很简单

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
#include <vector>
class Solution {
public:vector<int> res;vector<int> preorderTraversal(TreeNode* root) {res.clear();if(root == nullptr) return res;//递归dfs(root);return res;}void dfs(TreeNode* root){if(root == nullptr)return;res.push_back(root->val);dfs(root->left);dfs(root->right);}
};

• 迭代法，用辅助栈，入栈顺序是右左中

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
#include <vector>
class Solution {
public:vector<int> res;vector<int> preorderTraversal(TreeNode* root) {res.clear();if(root == nullptr) return res;//迭代stack<TreeNode*> st;st.push(root);TreeNode* temp;while(!st.empty()){//访问栈顶temp = st.top();st.pop();res.push_back(temp->val);//前序 中左右 栈 先进后出 入栈 右左中if(temp->right) st.push(temp->right);if(temp->left) st.push(temp->left); }return res;}
};

• 统一迭代法

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
#include <vector>
class Solution {
public:vector<int> res;vector<int> preorderTraversal(TreeNode* root) {res.clear();if(root == nullptr) return res;//统一迭代法bfs(root);return res;}//统一迭代法void bfs(TreeNode* root){if(root == nullptr)return;stack<TreeNode*> st;st.push(root);TreeNode* temp;while(!st.empty()){temp = st.top();if(temp != nullptr){st.pop();if(temp->right) st.push(temp->right);if(temp->left) st.push(temp->left);st.push(temp);st.push(nullptr);//当前层结束}else {st.pop();temp = st.top();st.pop();res.push_back(temp->val);}}}
};

BM24 二叉树的中序遍历

描述：给定一个二叉树的根节点root，返回它的中序遍历结果。进阶：空间复杂度 O(n)，时间复杂度 O(n)。

• 统一迭代法，关键就是在中结点后面加一个空节点标记

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vector<int> result;vector<int> inorderTraversal(TreeNode* root) {result.clear();if(root == nullptr) return result;unitedbfs(root);return result;}void unitedbfs(TreeNode* root){if(root == nullptr) return;stack<TreeNode*> st;st.push(root);TreeNode* temp;while(!st.empty()){temp = st.top();st.pop();if(temp != nullptr){if(temp->right) st.push(temp->right);st.push(temp);st.push(nullptr);if(temp->left) st.push(temp->left);}else {//更新当前节点temp = st.top();st.pop();result.push_back(temp->val);}}}
};

• 递归法

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vector<int> result;vector<int> inorderTraversal(TreeNode* root) {result.clear();if(root == nullptr) return result;dfs(root);return result;}void dfs(TreeNode* root){if(root == nullptr) return;if(root->left) dfs(root->left);result.push_back(root->val);if(root->right) dfs(root->right);}
};

BM25 二叉树的后序遍历

描述:给定一个二叉树，返回他的后序遍历的序列。后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

• 统一迭代法

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vector<int> result;vector<int> postorderTraversal(TreeNode* root) {result.clear();if(root == nullptr) return result;//dfs(root);unitedbfs(root);return result;}void unitedbfs(TreeNode* root){stack<TreeNode*> st;if(root != nullptr) st.push(root);TreeNode* temp;while(!st.empty()){temp = st.top();st.pop();if(temp != nullptr){st.push(temp);st.push(nullptr);if(temp->right) st.push(temp->right);if(temp->left) st.push(temp->left);}else {temp = st.top();st.pop();result.push_back(temp->val);}}}void dfs(TreeNode* root){if(root == nullptr) return;if(root->left) dfs(root->left);if(root->right) dfs(root->right);result.push_back(root->val);}
};

• 递归法

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vector<int> result;vector<int> postorderTraversal(TreeNode* root) {result.clear();if(root == nullptr) return result;dfs(root);return result;}void dfs(TreeNode* root){if(root == nullptr) return;if(root->left) dfs(root->left);if(root->right) dfs(root->right);result.push_back(root->val);}
};

BM26 求二叉树的层序遍历

• 迭代法
  和上面三个题不一样的地方来了，这里的层序遍历用队列。队列存放当前层的结点，for循环逐个遍历队列，每一层通过队列的大小（节点个数）来控制。

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vector<vector<int> > result;vector<vector<int> > levelOrder(TreeNode* root) {result.clear();if(root == nullptr) return result;queue<TreeNode* > que;que.push(root);TreeNode* cur;int size = 0;while(!que.empty()){vector<int> temp;size = que.size();for(int i=0; i<size; i++){cur = que.front();que.pop();temp.push_back(cur->val);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}result.push_back(temp);}return result;}
};

• 递归法，通过深度来控制

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:vector<vector<int> > result;vector<vector<int> > levelOrder(TreeNode* root) {result.clear();if(root == nullptr) return result;int depth = 0;dfs(root, depth);return result;}void dfs(TreeNode* root, int depth){if(root == nullptr) return;if(result.size() == depth) result.push_back(vector<int>{});result[depth].push_back(root->val);if(root->left) dfs(root->left, depth+1);if(root->right) dfs(root->right, depth+1);}
};

BM27 按之字形顺序打印二叉树

• 栈实现，两个栈，一个保存从左到右的结点，一个保存从右到左的节点。处理每个栈的时候有点层序遍历的意思，遍历当前栈的所有节点，同时把下一层的结点保存在另外一个栈中。可以用for或者while实现。

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
#include <iterator>
#include <ratio>
#include <stack>
class Solution {
public:vector<vector<int> > result;vector<vector<int> > Print(TreeNode* pRoot) {result.clear();if(pRoot == nullptr) return result;stackdone(pRoot);return result;}void stackdone(TreeNode* node){stack<TreeNode*> st1;stack<TreeNode*> st2;vector<int> v;TreeNode* cur;if(node != nullptr) st1.push(node);while(!st1.empty() || !st2.empty()){if(!st1.empty()){//左到右v.clear();int size = st1.size();for(int i=0; i<size; i++){cur = st1.top();//当前结点v.push_back(cur->val);//保存当前结点值//栈 先进后出 下一层在st2 入栈顺序是左 右；出栈就是右 左if(cur->left) st2.push(cur->left);if(cur->right) st2.push(cur->right);st1.pop();}result.push_back(v);}if(!st2.empty()){//从右到左v.clear();while(!st2.empty()){cur = st2.top();v.push_back(cur->val);if(cur->right) st1.push(cur->right);if(cur->left) st1.push(cur->left);st2.pop();}result.push_back(v);}}}
};

• 队列实现，也是遍历当前队列的所有节点，同时把下一层的结点保存在另外一个队列中。如果当前层是偶数，从左往右，尾部保存结点值；奇数，从右往左，头部保存结点值。

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
#include <iterator>
#include <ratio>
#include <stack>
class Solution {
public:vector<vector<int> > result;vector<vector<int> > Print(TreeNode* pRoot) {result.clear();if(pRoot == nullptr) return result;queuedone(pRoot);return result;}void queuedone(TreeNode* node){queue<TreeNode*> que;vector<int> v;TreeNode* cur;if(node != nullptr) que.push(node);int size = 0, depth = 0;while (!que.empty()) {size = que.size();v.clear();for(int i=0; i<size; i++){cur = que.front();que.pop();if(cur == nullptr) continue;//空元素跳过que.push(cur->left);que.push(cur->right);if(depth % 2 == 0) v.push_back(cur->val);else v.insert(v.begin(), cur->val);}depth++;if(!v.empty()) result.push_back(v);}}
};

BM28 二叉树的最大深度

描述：求给定二叉树的最大深度，深度是指树的根节点到任一叶子节点路径上节点的数量。最大深度是所有叶子节点的深度的最大值。（注：叶子节点是指没有子节点的节点。）
数据范围：0 ≤ n ≤ 100000,树上每个节点的val满足 ∣val∣≤100
要求： 空间复杂度 O(1),时间复杂度 O(n)

• 补充：
  使用前序求的就是深度，使用后序求的是高度。
  二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
  而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

• 递归法
  先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {int res = 0;if(root == nullptr) return res;res = dfs(root);return res;}int dfs(TreeNode* root){if(root == nullptr) return 0;int leftdepth = dfs(root->left);int rightdepth = dfs(root->right);int res = max(leftdepth, rightdepth) + 1;return res;}
};

• 迭代法，队列，层序遍历

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {int res = 0;if(root == nullptr) return res;//res = dfs(root);res = bfs(root);return res;}int bfs(TreeNode* root){if(root == nullptr) return 0;queue<TreeNode*> que;que.push(root);int dep = 0, size = 0;TreeNode* temp;while(!que.empty()){size = que.size();dep++;for(int i=0; i<size; i++){temp = que.front();que.pop();if(temp->left) que.push(temp->left);if(temp->right) que.push(temp->right);}}return dep;}int dfs(TreeNode* root){if(root == nullptr) return 0;int leftdepth = dfs(root->left);int rightdepth = dfs(root->right);int res = max(leftdepth, rightdepth) + 1;return res;}
};

BM29 二叉树中和为某一值的路径(一)

• 减法，递归

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int sum) {if(root == nullptr) return false;return dfs(root, sum - root->val);}bool dfs(TreeNode* cur, int target){//遍历到叶子节点 且为0 用减法//当前节点为叶子节点并且目标路径存在时if(cur->left == nullptr && cur->right == nullptr && target == 0) return true;//当前节点为叶子节点并且目标路径 不存在时if(cur->left == nullptr && cur->right == nullptr) return false;// 对左右分支进行 dfsif(cur->left){target -= cur->left->val;if(dfs(cur->left, target)) return true;target += cur->left->val;}if(cur->right){target -= cur->right->val;if(dfs(cur->right, target)) return true;target += cur->right->val;}return false;}
};

加法，递归

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int sum) {if(root == nullptr) return false;int res = 0;return dfs_add(root, sum, res);}bool dfs_add(TreeNode* cur, int sum, int res){if(cur == nullptr) return false;res += cur->val;if(!cur->left && !cur->right && res == sum) return true;return dfs_add(cur->left, sum, res) || dfs_add(cur->right, sum, res);        }
};

BM30 二叉搜索树与双向链表

描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

递归法，看解答的，变成双向链表，cur左指针指向上一个结点pre，pre的右指针指向cur：

1. 二叉搜索树的最左叶子节点
2. 中序遍历，左中右

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:TreeNode* pre;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;TreeNode* cur = pRootOfTree;while(cur->left) cur = cur->left;inorder(pRootOfTree);return cur;}void inorder(TreeNode* root){if(root == nullptr) return;inorder(root->left);//左//中 修改指向root->left = pre;if(pre)pre->right = root;pre = root;//更新pre 指向当前结点，作为下一个结点的前继inorder(root->right);}
};

用栈，迭代

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:TreeNode* pre = nullptr;TreeNode* head = nullptr;stack<TreeNode*> st;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;stackdone(pRootOfTree);return head;}void stackdone(TreeNode* root){while(!st.empty() || root != nullptr){//找到表头while(root != nullptr){st.push(root);root = root->left;}if(!st.empty()){//取出栈的结点root = st.top();st.pop();//第一次出栈的是表头if(pre == nullptr)head = root;else //建立双向连接{pre->right = root;root->left = pre;	}pre = root;//更新结点root = root->right;//连接链表}}}
};

最后两题，要再写写。