二叉树最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
解题思路,这道题其实和求二叉树的深度一样,只需要加上判断条件是否提前结束循环。
判断依据就是当前节点是否为叶节点,一样的有两种方法, BFS 和 DFS。
AC代码:
/**
* 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) {}
* };
*/
//BFS
class Solution {
public:
bool isLeaves(TreeNode* root) {
if(root && !root->left && !root->right) return true;
return false;
}
int minDepth(TreeNode* root) {
if(root == nullptr) return 0;
std::queue<TreeNode*> qt;
qt.push(root);
int depth = 0;
while(!qt.empty()) {
depth++;
for(int n = qt.size(); n > 0; --n) {
TreeNode* check = qt.front();
qt.pop();
if(isLeaves(check)) return depth;
if(check->left) qt.push(check->left);
if(check->right) qt.push(check->right);
}
}
return depth;
}
};
//DFS
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr) return 0;
if(!root->left && !root->right) return 1;
return (((root->left) && (root->right)) ? min(minDepth(root->left), minDepth(root->right))
:(root->left) ? minDepth(root->left) : minDepth(root->right)) + 1;
}
};
路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
解题思路,关于树的搜索既可以用广度搜索,也可以用深度搜索.这道题用递归代码量是最少的.而且深度搜索刚好符合傻瓜式的一条条路径搜索.
因为二叉树每个叶节点到根节点的路径是唯一的,也就是每个叶节点的路径总和是固定的,所以在 DFS 搜索的时候一起将路径总和加上去,然后判断叶节点是否有等于目标和.
在解题中需要注意的就是节点的值有正负数之分,所以不能利用大于小于 sum 提前结束递归.
/**
* 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 pathSum = 0;
bool DFS(TreeNode* root) {
if(!root->left && !root->right) {
if(root->val == pathSum )return true;
else return false;
}
if(root->left) root->left->val += root->val;
if(root->right) root->right->val += root->val;
return ((root->left) && (root->right)) ? (DFS(root->left)||DFS(root->right))
:(root->left) ? DFS(root->left) : DFS(root->right);
}
bool hasPathSum(TreeNode* root, int sum) {
if(root == nullptr) return false;
pathSum = sum;
return DFS(root);
}
};
路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
看到需要把路径打印出来, 也就是表明不能破坏原来二叉树的值, 所以我们需要一个新的 vector 来记录路径, 然后到叶节点时用 accumulate 函数判断当前 vector 的和是否等于给定值.
后面想到用 accumulate 函数需要遍历一次数组, 会耗费时间. 可以用数组的第一个值记录总和, 这样就可以直接拿第一个值比较.
但是没想到这两种方法的耗时竟然是一样的… 有点疑惑…
/**
* 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>> mRes;
int mSum = 0;
void findPath(TreeNode* root, vector<int> path) {
if(!root->left && !root->right) {
if(accumulate(path.begin(), path.end(), 0) == mSum) {
mRes.push_back(path);
}
return;
}
if(root->left) {
path.push_back(root->left->val);
findPath(root->left, path);
path.pop_back();
}
if(root->right) {
path.push_back(root->right->val);
findPath(root->right, path);
path.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(root == nullptr) return mRes;
mSum = sum;
vector<int> pathVI;
pathVI.push_back(root->val);
findPath(root, pathVI);
return mRes;
}
};
//改良版
class Solution {
public:
vector<vector<int>> mRes;
int mSum = 0;
void findPath(TreeNode* root, vector<int> path) {
if(!root->left && !root->right) {
if(*(path.begin()) == mSum) {
mRes.push_back(vector<int>(path.begin()+1, path.end()));
}
return;
}
if(root->left) {
*(path.begin()) += root->left->val;
path.push_back(root->left->val);
findPath(root->left, path);
path.pop_back();
*(path.begin()) -= root->left->val;
}
if(root->right){
*(path.begin()) += root->right->val;
path.push_back(root->right->val);
findPath(root->right, path);
path.pop_back();
*(path.begin()) -= root->right->val;
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(root == nullptr) return mRes;
mSum = sum;
vector<int> pathVI;
pathVI.push_back(root->val);
pathVI.push_back(root->val);
findPath(root, pathVI);
return mRes;
}
};
二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
解题思路，右节点移到左节点的最右节点，然后左节点移到右节点，左节点置为 null。
/**
* 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:
void flatten(TreeNode* root) {
TreeNode* mRoot = root;
while(mRoot != nullptr) {
TreeNode* tmp = mRoot->right;
mRoot->right = mRoot->left;
mRoot->left = nullptr;
TreeNode* mR = mRoot;
while(mR->right != nullptr) mR = mR->right;
mR->right = tmp;
mRoot = mRoot->right;
}
}
};
不同的子序列
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
解题思路，刚开始想的是利用递归切割字符串，但是既然是困难的标签，所以在点击提交的时候已经做好了超时的准备。
结果当然是超时，想了一下，单独的切割递归是做了很多重复的工作。
最后想到的办法是，检测字符串 t 每个字符在字符串 s 出现的位置。然后根据每个字符的位置来生成有多少种组合方式。
最后利用动态规划的方式计算最终有多少种组合。
eg.
string s = “rabbbit”, t = “rabbit”;
那么字符串 t 每个字符在 s 中出现的位置如下(如果有未出现的直接返回0)：
0 1 2 3 4 2 3 4 5 6
t 中的第一个字符如果存在那么肯定是可以达到的，所以为 1；然后根据动态规划，依次为 t 中的字符赋值，最后可得到：
1 1 1 1 1 0 1 2 3 3
最后一步，把 t 中的最后一个字符的值累加得到总和。
class Solution {
public:
int res = 0;
map<char, vector<int>> ms;
int numDistinct(string s, string t) {
if(t.size() == 0) return 1;
if(s.size() == 0) return 0;
for(int i = 0; i < s.size(); ++i) {
if(ms.find(s[i]) == ms.end()) {
vector<int> vi = {i};
ms[s[i]] = vi;
}else {
ms[s[i]].push_back(i);
}
}
vector<vector<int>> vvi;
vector<vector<long long int>> vviRes;
for(char c : t) {
if(ms.find(c) != ms.end()) {
vvi.push_back(ms[c]);
vector<long long int> tmp(ms[c].size(), 0);
vviRes.push_back(tmp);
}else{
return 0;
}
}
for(int i = 0; i < t.size(); ++i) {
for(int j = 0; j < vvi[i].size(); ++j) {
if(i == 0) {
vviRes[i][j] = 1;
}else {
for(int k = 0; k < vvi[i-1].size() && vvi[i][j] > vvi[i-1][k]; ++k) {
vviRes[i][j] += vviRes[i-1][k];
}
}
}
}
for(int i = 0; i < vvi[t.size()-1].size(); ++i) {
res += vviRes[t.size()-1][i];
}
return res;
}
};
填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
解题思路，第一反应就是利用队列遍历，但是这样不符合题目要求的“常量级额外空间”，所以此路不通。
看到题目又提示了一手递归的思想，然后想到好像的确是可以利用常量空间递归实现。实现思路为
1 利用父节点实现两个子节点的 next 指针；root->left->next = root->right;
2 利用父节点的 next 指针实现相连的右节点和左节点的 next 指针； root->right->next = root->next->left;
/*
// 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 == NULL) return NULL;
Node* opeStart = root;
Node* opeScan = root;
while(opeStart->left != NULL) {
opeScan->left->next = opeScan->right;
if(opeScan->next != NULL) {
opeScan->right->next = opeScan->next->left;
}
opeScan = opeScan->next;
if(opeScan == NULL) {
if(opeStart->left != NULL) {
opeStart = opeStart->left;
opeScan = opeStart;
}else {
opeStart = NULL;
}
}
}
return root;
}
};
填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
这道题与上一道不同的地方就是上一道是完美二叉树，而这道是普通的二叉树。
解题思路还是和上一道一样，只不过会加一手判断条件，还是利用广度循环的思想，对每一层的节点进行处理。
对一层节点处理包括：保存下一层头结点用于下一次遍历，保存遍历节点对 next 的赋值。
/*
// 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 == NULL) return NULL;
Node* opeStart = NULL;
Node* opeNextScan = NULL;
Node* opeScan = root;
while(opeScan) {
//判断左节点
if(opeScan->left) {
if(opeStart) {
opeNextScan->next = opeScan->left;
opeNextScan = opeNextScan->next;
}else {
opeStart = opeScan->left;
opeNextScan = opeStart;
}
}
//判断右节点
if(opeScan->right) {
if(opeStart) {
opeNextScan->next = opeScan->right;
opeNextScan = opeNextScan->next;
}else {
opeStart = opeScan->right;
opeNextScan = opeStart;
}
}
//进行下一次判断
if(!opeScan->next) {
if(opeStart) {
opeScan = opeStart;
opeStart = NULL;
opeNextScan = NULL;
}else {
opeScan = NULL;
}
}else {
opeScan = opeScan->next;
}
}
return root;
}
};
杨辉三角
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
解题思路，找到杨辉三角的推导式和通项公式，然后赋值。
推导式为 $a_{11} = 1; a_{ii} = 1; a_{ij} = a_{(i-1)(j-1)} + a_{(i-1)j}; i >= j$
且通项公式为 $C(n,i) = \frac{n!}{(i!*(n-i)!)}$
根据通项公式可得， $a_{i+1} = \frac{n-i}{i+1} * a_{i}$
//根据推导式
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
for(int i = 0;i < numRows; ++i) {
vector<int> row(i+1, 1);
if(i != 0){
for(int j = 1; j < i; ++j) {
row[j] = res[i-1][j-1] + res[i-1][j];
}
}
res.push_back(row);
}
return res;
}
};
杨辉三角 II
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
解题思路，找到杨辉三角的通用表达式，然后赋值。和上一题一样
//根据通项公式
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> res;
//用long防止后面计算溢出
long tmp = 1;
for(int i = 0; i <= rowIndex; ++i) {
res.push_back((int)tmp);
tmp = tmp * (rowIndex - i) / (i+1);
}
return res;
}
};
三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
输入：triangle = [[-10]]
输出：-10
提示：
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
解题思路，因为不需要保存原数组以及路线，所以只需要在原数组上面更新当前最短路径和，最后筛选出最后的路径和。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int res = INT_MAX;
if(triangle.size() <= 1) {
res = (triangle.size() == 1) ? triangle[0][0] : 0;
}else {
for(int i = 1; i < triangle.size(); ++i) {
for(int j = 0; j < triangle[i].size(); ++j) {
if(j == 0) {
triangle[i][j] += triangle[i-1][0];
}else if(j == triangle[i].size()-1) {
triangle[i][j] += triangle[i-1][j-1];
}else {
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
}
if(i == triangle.size()-1) {
res = min(res, triangle[i][j]);
}
}
}
}
return res;
}
};
