LeetCode刷题-115. 不同的子序列
题目链接：115. 不同的子序列
¶题解：
熟悉的动态规划又来了！
¶题目简述：
给定两个字符串，问按顺序可以从第一个字符串中找到多少种方案可以组成第二个字符！
¶题解：
**动态规划：**同样字符串前面加空格更好的处理边界问题！
状态表示： 两个字符串，使用二维数组f[i][j]表示s串前i个字符和t串前j个字符的方案数
状态计算： 两种情况：
s[i] != t[j]：则当前状态f[i][j] = f[i - 1][j]，即为s串前i - 1个字符和t串前j个字符的方案数
s[i] == t[j]：则当前状态f[i][j] = f[i - 1][j] + f[i - 1][j - 1]，即可以匹配最后一个字符即为f[i - 1][j - 1]，也可以不匹配即为f[i - 1][j]
最终答案： f[n][m]
边界条件： f[i][0] = 1，即s串前i个字符和t串前0个字符（空格）的方案数都是1，s一定有一个空格（开始部分）。
时间复杂度：O(nm)
¶AC代码：
12345678910111213141516class Solution {public: i ...
LeetCode刷题-114. 二叉树展开为链表
题目链接：114. 二叉树展开为链表
¶题解：
找规律？
¶题目简述：
讲一个二叉树变为一个链表，具体查看题目链接！
¶题解：
思路：
若当前点存在左子树，则将左子树右链插入当前节点的右儿子
否则，当前节点走到右子树
就是每次将从左上到右下方向的链插入到该父节点的右链！
时间复杂度：外层循环遍历每个节点一次为O(n)，内存循环会将每个右链遍历一次，每个节点最多被遍历两次，为O(n)
¶AC代码：
1234567891011121314151617181920212223242526/** * 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) {} * ...
LeetCode刷题-113. 路径总和 II
题目链接：113. 路径总和 II
¶题解：
和上一题类似，简单递归！
¶题目简述：
和上一题类似，多加了一个记录路径的要求！
¶题解：
递归：
根节点为空直接返回
将当前节点加入路径
答案条件：到了叶子结点并且sum减到了0
左子树不空递归左子树
右子树不空递归右子树
将当前加点删掉，恢复状态
由于要走遍所有情况，所以和上一题相比少了一个都不空的情况！
时间复杂度：遍历所有节点为O(n)，记录所有路径为O(n)，总复杂度为O(n^2)
¶AC代码：
1234567891011121314151617181920212223242526272829/** * 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: vec ...
LeetCode刷题-112. 路径总和
题目链接：112. 路径总和
¶题解：
简单递归！
¶题目简述：
给定一个二叉树和一个目标值，问是否有从根节点到叶子节点的和为目标值的线路！
¶题解：
**递归：**从根节点开始减，直到叶子节点判断是否为0即可，几种情况
根节点为空：返回false
左右子树都空：返回!sum
左右子树都不空：左边符合直接返回true，否则处理右边
左右子树一个空一个非空：放回该方向是否符合！
注意：
注释部分为分开写法
可以合并为最后一句：左边存在且符合直接返回，不符合继续看右边是否存在，存在则看是否符合，最终返回！
时间复杂度：遍历每个节点一次，为O(n)
¶AC代码：
123456789101112131415161718192021/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) ...
LeetCode刷题-111. 二叉树的最小深度
题目链接：111. 二叉树的最小深度
¶题解：
求二叉树的深度问题！
¶题目简述：
求二叉树的最小深度！
¶题解：
**简单递归：**最小深度一定是左右子树中较小的一个，递归去处理，分几种情况：
根节点为空：返回0
左右子树都为空：返回1
左右子树都非空：返回左右子树的较小深度加一
左右子树一个空一个非空：返回该子树深度加一
时间复杂度：遍历每个节点一次，为O(n)
¶AC代码：
12345678910111213141516171819/** * 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 minDepth(TreeNode* root) { if(!root) return 0; ...
LeetCode刷题-110. 平衡二叉树
题目链接：110. 平衡二叉树
¶题解：
平衡二叉树的判断！
¶题目简述：
给定一棵二叉树判断是否是平衡二叉树！
¶题解：
平衡二叉树定义：所有 左右子树高度差不超过1
思路：根据定义来求解
求每个左右子树的高度，判断高度差是否大于1即可，即abs(lh - rh) > 1
二叉树高度，同之前的求高度问题，左右高度最大值加一即可，即max(lh, rh) + 1
其实就是递归求二叉树高度问题多了一个变量来存储是否差值超过了1！
时间复杂度：每个节点遍历一次，为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: ...
LeetCode刷题-109. 有序链表转换二叉搜索树
题目链接：109. 有序链表转换二叉搜索树
¶题解：
同样是构造二叉搜索树！链表比较麻烦一点！
¶题目简述：
将有序链表构造为高度平衡的二叉搜索树！
¶题解：
链表构造二叉树会麻烦一点！
**思路：**总思路和数组相同，递归解决，仍是区间角度考虑！
与数组不同，这个无法使用正常的区间，由于是链表，只能使用一个指针指向区间起点！
为了找到节点数，需要遍历一次求长度
长度为1直接返回当前节点（也是为了处理边界问题）
找到中间节点：我们应该扎到左子树区间的终点cur，这样可以通过改点找到右子树的起点cur->next->next，循环n / 2 - 1次即可，保证左边比右边多一（偶数时）或者相等（奇数时），可以处理边界条件（当节点为2时，防止左右子树起点都不正确）
先处理右子树，在处理左子树，否则左子树的区间长度就不是一半了，变成整个区间了，不正确！先处理右子树，处理完将cur->next = NULL将区间分为两段head ~ cur， cur->next->next ~ NULL
最后返回当前根节点root，区间为空返回NULL
时间复杂度：递归 ...
LeetCode刷题-108. 将有序数组转换为二叉搜索树
题目链接：108. 将有序数组转换为二叉搜索树
¶题解：
构造二叉搜索树问题！
¶题目简述：
将有序数组构造为高度平衡的二叉搜索树！
¶题解：
仍然从区间角度去考虑递归子问题来解决！
思路：
对于有序数组，二叉搜索树的根节点一定是区间的中心，即 l + r >> 1
根节点：root = new TreeNode(nums[mid])
左子树区间：l, mid - 1
右子树区间：mid + 1, r
l > r区间为空返回NULL
关于高度平衡即左右子树高度差小于一的证明：
很明显，和二分一样，高度一定是Log2 (n + 1)上取整的！
关于更加数学化的证明：参考 y 总证明！点击这里！
时间复杂度：每个节点遍历一次，为O(n)
¶AC代码：
1234567891011121314151617181920212223/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; ...
LeetCode刷题-107. 二叉树的层次遍历 II
题目链接：107. 二叉树的层次遍历 II
¶题解：
和第102道题一样！
¶题目简述：
二叉树层次遍历，要求先遍历最底层！
¶题解：
嗯，按照正常顺序层序遍历，最后将答案进行反转即可！
正常层序遍历思路参见第102道题题解！使用博客搜索框搜索即可！
时间复杂度：O(n)
¶AC代码：
1234567891011121314151617181920212223242526272829303132/** * 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>> levelOrderBottom(TreeNode* root) { vector< ...
LeetCode刷题-106. 从中序与后序遍历序列构造二叉树
题目链接：106. 从中序与后序遍历序列构造二叉树
¶题解：
二叉树的后中序构造二叉树！
¶题目简述：
给定二叉树的后中序遍历来构造一颗二叉树！
¶题解：
后序遍历：根节点最后遍历
中序遍历：通过后序遍历得到的值找到中序序列的根节点下标位置，将序列分为左右子树
与前中序一样，详细见上一道题！
这里只给出下标对应关系：
左子树下标： pl, k - 1 - il + pl, il, k - 1
右子树下标： k - 1 - il + pl + 1, pr - 1, k + 1, ir
下标计算同上一道前中序计算，参考上一题！
时间复杂度：同样适用哈希表将复杂度降为O(n)
¶AC代码：
12345678910111213141516171819202122232425/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), le ...
LeetCode刷题-105. 从前序与中序遍历序列构造二叉树
题目链接：105. 从前序与中序遍历序列构造二叉树
¶题解：
二叉树的前中序构造二叉树！
¶题目简述：
给定二叉树的前中序遍历来构造一颗二叉树！
¶题解：
必会知识：
前序遍历的第一个节点一定是根节点
中序遍历可以借助前序遍历得到的根节点将区间分为左右子树两部分
看明白了吧，按照左右子树区间进行递归即可！
思路：
由于我们要从中序遍历找前序遍历得到的根节点，所以事先将中序遍历的节点和下标关系存储于哈希表，使得可以在O(1)时间查询到下标
根节点：前序遍历的第一个节点，root = new TreeNode(preorder[pl])
当没有节点时即pl > pr，返回NULL
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)，参数分别为：前序，中序，前序起始下标，前序终止下标，中序起始下标，中序终止下标
k为中序遍历根节点下标，创建一个根节点，左右子树递归得到
左子树下标： pl + 1, k ...
LeetCode刷题-104. 二叉树的最大深度
题目链接：104. 二叉树的最大深度
¶题解：
二叉树深度问题！
¶题目简述：
求二叉树的最大深度！
¶题解：
很简单的！
思路： 深度对于根结点来说就是左子树和右子树的最大深度加一即可，则我们递归去求其高度！
时间复杂度：O(n)
¶AC代码：
12345678910111213141516/** * 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 maxDepth(TreeNode* root) { if(!root) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; ...
