LeetCode刷题-103. 二叉树的锯齿形层次遍历
题目链接：103. 二叉树的锯齿形层次遍历
¶题解：
同样是二叉树层序遍历！
¶题目简述：
给定一个二叉树进行层序遍历，但是要保证左右，右左顺序来回交替遍历！
¶题解：
**思路：**和上一题一模一样，多了一个条件，即当层数（从0开始）为奇数时，将遍历得到的vector反转一次即可！
时间复杂度：O(n)
¶AC代码：
123456789101112131415161718192021222324252627282930313233/** * 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>> zigzagLevelOrder(TreeNode* root) ...
LeetCode刷题-102. 二叉树的层序遍历
题目链接：102. 二叉树的层序遍历
¶题解：
二叉树层序遍历，很巧的思路！
¶题目简述：
给定一个二叉树，返回一个层序遍历的二维vector!
¶题解：
很明显是一个BFS：
思路：
宽搜进行遍历每一层
遍历当前层时将下一层全部入队即可，循环次数就是当前层的节点数
时间复杂度：O(n)
¶AC代码：
12345678910111213141516171819202122232425262728293031/** * 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>> levelOrder(TreeNode* root) { vector& ...
LeetCode刷题-101. 对称二叉树
题目链接：101. 对称二叉树
¶题解：
简单递归！
¶题目简述：
给定一棵二叉树判断是否是对称的！
¶题解一：递归
对于根节点来说，对称意味着左子树和右子树一致。
对于左子树和右子树，即保证左子树的左子树和右子树的右子树一致并且左子树的右子树和右子树的左子树一致即可！
则我们可以递归分解为子问题来解决！
递归DFS：
dfs(p->left, q->right) && dfs(p->right, q->left);
最终答案：dfs(root->left, root->right)
递归出口：和前几道题一样：
!p && !q：都空返回true
!p || !q || p->val != q->val：一个空一个非空，或者都不空但值不相同返回false
注意：
根节点为空，直接返回true
时间复杂度：每个节点只被遍历一次，为O(n)
¶AC代码一：
123456789101112131415161718192021/** * Definition for a binary ...
LeetCode刷题-100. 相同的树
题目链接：100. 相同的树
¶题解：
简单判断两颗二叉树是否相同！
¶题目简述：
给定两颗二叉树，判断是否相同！
¶题解一：DFS
两树相同，即对应的左子树相同，对应的右子树相同即可！
思路：
左子树相同，并且右子树相同即可，即isSameTree(p->left, q->left) && isSameTree(p->right, q->right)
递归出口：
两子树都空，返回true
一子树空，一子树不空，或者两子树都不空但值不同，返会false
**时间复杂度：**所有节点遍历一次， 为 O(n)
¶AC代码一：
12345678910111213141516171819/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) ...
LeetCode刷题-99. 恢复二叉搜索树
题目链接：99. 恢复二叉搜索树
¶题解：
一个占用空间为O(1)的新的二叉树遍历算法面世！
¶题目简述：
交换了两个节点的二叉搜索树，需要我们将其恢复回来！
要求空间复杂度为O(1)
¶题解一：空间O(n)
先给出空间占用为O(n)的算法！
当前很好想，就是使用递归或非递归的栈来实现！
现在先简单介绍一下这题怎么能找出两个被交换的节点？
我们知道，二叉搜索树中序遍历有序，若交换两个点会造成逆序对出现，我们就根据逆序对来找两个点的位置！
两种情况：
交换两元素相邻：如 1 3 2 4 5 6 7，即3，2逆序对，就是交换的两个节点
交换两元素不相邻：如 1 6 3 4 5 2 7，即6，2交换，对于相邻元素的逆序对有两个，即6 3和5 2，即交换位置为第一个相邻元素逆序对的第一个值和第二个相邻元素逆序对的第二个值！
具体做法：
与中序遍历递归写法一样，多一个指针指向当前节点的上一个节点last，每次进行相邻元素判断是否是逆序对，是则更新两个交换指针first, second，之后再次遇到只更新second即可
最后进行两节点值的交换swap(first->val, ...
LeetCode刷题-98. 验证二叉搜索树
题目链接：98. 验证二叉搜索树
¶题解：
判断是否是二叉搜索树！递归写法有点意思！
¶题目简述：
判断是否是二叉搜索树！
¶题解一：非递归
我们知道二叉搜索树中序遍历后是有序的！
思路：
中序遍历二叉搜索树
两个变量指向一前一后
若后面大于前面直接返回false
时间复杂度：O(n)
¶AC代码一：
12345678910111213141516171819202122232425262728/** * 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 isValidBST(TreeNode* root) { TreeNode* pre = NULL; stack<Tr ...
LeetCode刷题-97. 交错字符串
题目链接：97. 交错字符串
¶题解：
简单动态规划！
¶题目简述：
给定三个字符串，前两个字符串能否组成第三个字符串！
¶题解：
动态规划：
状态表示： 两个字符串，使用二维数组f[i][j]，s1串的前i个字符串和s2串的前j个字符能否构成s3串的前i + j个字符！
**状态计算：**同样的套路，只考虑最后一步，即能交错形成的条件：
当s1[i] == s3[i + j]时：s1串的前i - 1个和s2的前j个匹配
当s2[j] == s3[i + j]时：s1串的前i个和s2的前j - 1个匹配
综上所述： 状态转移方程为：f[i][j] = f[i - 1][j] || f[i][j - 1]
初始转态： f[0][0] == true 同样取决于能否将所有状态全部计算对！不解释了！
最终结果： f[n][m]
时间复杂度：O(n^2)
¶AC代码：
12345678910111213141516171819class Solution {public: bool isInterleave(string s1, string s2, string s3) { ...
LeetCode刷题-96. 不同的二叉搜索树
题目链接：96. 不同的二叉搜索树
¶题解：
本题就是求卡特兰数，这里使用动态规划来写！
¶题目简述：
求n个节点可以构成二叉搜索树的个数！
¶题解：
可以直接利用卡特兰数公式来求，似乎不太好求！
这里使用动态规划来求：
和上一道类似，同样是乘法原理，j表示长度为1 ~ i的根节点的位置，左子树的长度为 j - 1，右子树的长度为i - j
状态表示：f[i]表示i长度的二叉搜索树个数
状态计算： f[i] += f[j - 1] * f[i - j]（j可以取该区间任何位置，累加关系） 乘法原理，左边乘以右边
初始转态： f[0] = 1，同样这个初始状态由能否使得所有状态算对即可！当i, j都为1时，f[i] = f[j - 1] * f[i - j] 应该为1，即f[0] = 1
最终答案： f[n] 即n长度的二叉搜索树个数
注意：对于1 ~ 5 和2 ~ 6可以构成的二叉搜索树是一样的，可以这样想，将1 ~ 5构成的二叉搜索树根据对应关系可以全部替换为2 ~ 6，即二叉搜索树的个数时有区间长度决定的！
时间复杂度：O(n^2)
¶AC代码：
1234567891011 ...
LeetCode刷题-95. 不同的二叉搜索树 II
题目链接：95. 不同的二叉搜索树 II
¶题解：
生成所有二叉搜索树！有意思的题！
¶题目简述：
给定一个序列，生成所有二叉搜索树的序列！
¶题解：
递归DFS：
对于一个区间的二叉搜索树，我们只需要枚举根节点所在的位置即可，通过递归一步步构建不同的二叉搜索树！
从1 ~ n开始搜索
枚举根节点位置为l ~ r
递归左子树l ~ i - 1，右子树i + 1 ~ r
由于相当于乘法原理，左子树随便一种情况和右子树随便一种情况组合都是一个合法的二叉搜索树
左子树取一种情况，右子树取一种情况，构建根节点，连接起来形成当前结构的二叉搜索树
将当前所有二叉搜索树插入res并返回
递归终止条件：
l > r：即为空树，返回NULL
n == 0：即输入为0，直接返回空容器{}
注意：
根节点一定要随用随创建，若创建第一层for循环，会导致覆盖情况发生，由于存储的是指针，最后存储将都会是一样的一个二叉树
此处的res不能创建到全局的，那样无法完成下一层向上一层的传递
时间复杂度：是卡特兰数，n个节点构成的二叉搜索树种类是卡特兰数，即 C2nn / n + 1 ！对于n个 ...
LeetCode刷题-94. 二叉树的中序遍历
题目链接：94. 二叉树的中序遍历
¶题解：
开始进入二叉树的世界！
¶题目简述：
给定一个二叉树，返回中序遍历序列！
¶题解：
中序遍历：即左根右的顺序去遍历！
递归：
从根节点开始遍历
遍历左子树
访问当前根节点
遍历右子树
递归到空节点返回
时间复杂度：O(n)
¶AC代码一：递归实现
1234567891011121314151617181920212223/** * 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<int> res; vector<int> inorderTraversal(TreeNode* root) { dfs(root); ...
LeetCode刷题-93. 复原IP地址
题目链接：93. 复原IP地址
¶题解：
带有剪枝的搜索，挺有意思！
¶题目简述：
给定一串数字，需要将其可以转化为的IP地址返回！
¶题解：
暴力搜索DFS：void dfs(string s, int u, int k, string path)
u：当前搜索到的位置
k：当前搜索的点的个数
path：当前状态下的IP地址
思路：
对于前导0的处理，即012，IP地址没有前导0的，这个已经见过很多次了，直接i > u && s[u] == '0'即可判断！
然后搜索下一位时保证下一位在0 ~ 255范围即为合法数字，否则直接return
下一个数的搜索要从上一个数的后一位开始，即i = u开始
终止条件：
u == s.size()：即搜到了字符串末尾
剪枝优化：u < s.size() && k == 4：即没有搜到最后，已经够了四个点
答案： u == s.size() && k == 4：即恰好组成一组IP地址，此时将该IP地址path最后的小数点去掉，即为答案
时间复杂度：一共n位，n - 1个 ...
LeetCode刷题-92. 反转链表 II
题目链接：92. 反转链表 II
¶题解：
又是链表操作题，记得要画图哦！
¶题目简述：
将一个链表的m ~ n位置进行翻转！
¶题解：
思路：
将m ~ n进行指针翻转
将m指向n的下一位， 将a指向n
如下图：
具体来说：
首先找到m的前一个位置a
让b指向m， c指向m的下一位，t指向c的下一位
接下来将m ~ n进行指针翻转，即让c指向b
然后b c指针顺次后移
最后将该链如上图所示，连起来！懒得解释了，看图吧！
时间复杂度：O(n)
¶AC代码：
123456789101112131415161718192021222324252627/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* reverseBetween(ListNode* he ...
