剑指offer43-56树_给定一个二叉树根结点-程序员宅基地
剑指 Offer II 043. 往完全二叉树添加节点
完全二叉树除了最后一行都是满的
方法：层序遍历获取第一个不完整的节点
初始化时将不完整的节点加入到队列当中
插入时从队列找最先插入的节点，看它是左节点为空还是右节点为空，如果右节点为空说明父节点满了，就将父节点从不完整队列中弹出来，如果左节点为空，不做处理。最后将当前插入的节点加入到不完整队列中
代码
class CBTInserter {
private:
queue<TreeNode*> que;
TreeNode* root;
public:
CBTInserter(TreeNode* root) {
//初始化完全二叉树和不完整队列
this->root = root;
que.push(root);
while (que.front()->left != nullptr && que.front()->right != nullptr) {
que.push(que.front()->left);
que.push(que.front()->right);
que.pop();
}
}
int insert(int v) {
//插入一个节点，需要保证为完全二叉树
TreeNode* node = new TreeNode(v);
TreeNode* fa = que.front();
if (fa->left == nullptr) {
fa->left = node;
}
else {
fa->right = node;
que.push(fa->left);
que.push(fa->right);
que.pop();
}
return fa->val;
}
TreeNode* get_root() {
//获得输的根节点
return this->root;
}
};
剑指 Offer II 044. 二叉树每层的最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
返回每层的最大值的节点
方法层次遍历，队列每次仅保存当前层的节点
在对每层进行遍历时，用队列.size()确定当前层的节点数量n，然后接一个for循环只处理n数量，将其加入孩子节点加入到队列中并求最大值
代码
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
if (root == nullptr) {
return {
};
}
vector<int> allMax;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
int curMax = INT_MIN;
for (int i = 0; i < size; ++i) {
TreeNode* node = que.front();
que.pop();
curMax = max(curMax, node->val);
if (node->left != nullptr) {
que.push(node->left);
}
if (node->right != nullptr) {
que.push(node->right);
}
}
allMax.push_back(curMax);
}
return allMax;
}
};
剑指 Offer II 045. 二叉树最底层最左边的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
找最下面的最左边节点的值，比如上面那图的7
解法：层序遍历
遍历每层时，用一个flag做标记，然后遍历每个节点的孩子节点，如果孩子节点并且flag未置1那么这个孩子节点就是它那一层的第一个节点。下面代码有点问题，将bottomLeft=0改为bottomeLeft=root->val;
代码
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
que.push(root);
int bottomLeft = root->val;
while (!que.empty()) {
int size = que.size();
bool flag = 0;
for (int i = 0; i < size; ++i) {
TreeNode* node = que.front();
que.pop();
/*if (i == 0) {
bottomLeft = node->val;
}*/
if (node->left != nullptr) {
if(node->left!=nullptr)
que.push(node->left);
if (flag == 0)
{
bottomLeft = node->left->val;
flag = 1;
}
}
if (node->right != nullptr) {
if(node->right!=nullptr)
que.push(node->right);
if (flag == 0)
{
bottomLeft = node->right->val;
flag = 1;
}
}
}
}
return bottomLeft;
}
};
剑指 Offer II 046. 二叉树的右侧视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
注意，并不是返回右节点的右节点，不可以只将右节点加入到里面，像下面第一个，返回的是1,2
解法一：层序遍历
代码
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (root == nullptr) {
return {
};
}
vector<int> view;
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; ++i) {
TreeNode* node = que.front();
que.pop();
if (i == size - 1) {
view.push_back(node->val);
}
if (node->left != nullptr) {
que.push(node->left);
}
if (node->right != nullptr) {
que.push(node->right);
}
}
}
return view;
}
};
剑指 Offer II 047. 二叉树剪枝
题目意思：减掉二叉树中所有节点的值为0的子树（如果0的子树中包含1，那么这个0不会被删除）
方法一：递归
在结尾：
代码
class Solution2 {
public:
TreeNode* pruneTree(TreeNode* root) {
//因为递归返回的bool值，因此在根节点需要有一步判断
return containOne(root) ? root : NULL;
}
bool containOne(TreeNode* root)
{
if (root == NULL) return false;
bool a = containOne(root->left);
bool b = containOne(root->right);
if (!a)root->left = NULL;
if (!b)root->right = NULL;
return root->val == 1 || a || b;
}
};
也可以用一个函数处理
上面这些都可以理解为后序遍历，最后处理的当前节点。
剑指 Offer II 048. 序列化与反序列化二叉树
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
题目意思实现两个函数，一个将string字符串（不是数组）实现为树结构返回根节点，一个是将根节点返回为string字符串。
方法：前序遍历
仅使用前序遍历无法确定一棵二叉树，因为不知道下一个是往下还是结束，那么加上空节点表示当前分支已经结束了，让它继续向下一个进行，因此要包含空节点才可以，因此序列化一个二叉树要将空也加入。
反序列化。
反序列化先将字符串按照逗号分成各个节点，然后前序递归
开始前序遍历
代码
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == nullptr) {
return "#";
}
string now = to_string(root->val);
string leftStr = serialize(root->left);
string rightStr = serialize(root->right);
return now + "," + leftStr + "," + rightStr;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
// 分割字符串
vector<string> dataArray{
"" };
for (auto& ch : data) {
if (ch == ',') {
dataArray.push_back("");
}
else {
dataArray.back().push_back(ch);
}
}
int i = 0;
return dfs(dataArray, i);
}
private:
TreeNode* dfs(vector<string>& strs, int& i) {
string str = strs[i];
i++;
if (str == "#") {
return nullptr;
}
TreeNode* node = new TreeNode(stoi(str));
node->left = dfs(strs, i);
node->right = dfs(strs, i);
return node;
}
template <class T>
void printVector(vector<T>ve) {
cout << "vector的内容为" << " ";
for (auto& ch : ve) {
cout << ch << " ";
}
cout << endl;
}
};
剑指 Offer II 049. 从根节点到叶节点的路径数字之和
给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
题目意思是将所有从根到叶子节点的路径的值加起来。
方法： 前序遍历（深度遍历）
代码
class Solution {
public:
int sumNumbers(TreeNode* root) {
return dfs(root, 0);
}
private:
int dfs(TreeNode* root, int path) {
if (root == nullptr) {
return 0;
}
path = path * 10 + root->val;
// 叶子节点
if (root->left == nullptr && root->right == nullptr) {
return path;
}
return dfs(root->left, path) + dfs(root->right, path);
}
};
方法二：层序遍历（广度优先）
维护两个队列，第一个队列存放节点，一个存放到该节点的拥有的值，比如1->2，第一个队列存放1 2
第二个队列存放1，12
代码
class Solution {
public:
int sumNumbers(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int sum = 0;
queue<TreeNode*> nodeQueue;
queue<int> numQueue;
nodeQueue.push(root);
numQueue.push(root->val);
while (!nodeQueue.empty()) {
TreeNode* node = nodeQueue.front();
int num = numQueue.front();
nodeQueue.pop();
numQueue.pop();
TreeNode* left = node->left;
TreeNode* right = node->right;
if (left == nullptr && right == nullptr) {
sum += num;
} else {
if (left != nullptr) {
nodeQueue.push(left);
numQueue.push(num * 10 + left->val);
}
if (right != nullptr) {
nodeQueue.push(right);
numQueue.push(num * 10 + right->val);
}
}
}
return sum;
}
};
剑指 Offer II 050. 向下的路径节点之和
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
题目意思：给一个二叉树，找所有的从上到下的路径，要求和为目标值，返回路径的条数
方法一：暴力穷举所有路径
使用深度遍历即前序遍历去枚举所有路径
代码
class Solution {
public:
int rootSum(TreeNode* root, int targetSum) {
if (!root) {
return 0;
}
int ret = 0;
if (root->val == targetSum) {
ret++;
}
ret += rootSum(root->left, targetSum - root->val);
ret += rootSum(root->right, targetSum - root->val);
return ret;
}
int pathSum(TreeNode* root, int targetSum) {
if (!root) {
return 0;
}
int ret = rootSum(root, targetSum);
ret += pathSum(root->left, targetSum);
ret += pathSum(root->right, targetSum);
return ret;
}
};
二叉树前缀和
简化问题为一维数据。
代码
class Solution {
public:
unordered_map<long long, int> prefix;
int dfs(TreeNode *root, long long curr, int targetSum) {
if (!root) {
return 0;
}
int ret = 0;
curr += root->val;
if (prefix.count(curr - targetSum)) {
ret = prefix[curr - targetSum];
}
prefix[curr]++;
ret += dfs(root->left, curr, targetSum);
ret += dfs(root->right, curr, targetSum);
prefix[curr]--;
return ret;
}
int pathSum(TreeNode* root, int targetSum) {
prefix[0] = 1;
return dfs(root, 0, targetSum);
}
};
剑指 Offer II 051. 节点之和最大的路径
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。
题目要求最大的路径和，这里并不是图的路径问题，子树中一定有个根节点
方法：递归
代码
class Solution {
private:
int maxSum = INT_MIN;
public:
int maxGain(TreeNode* node) {
if (node == nullptr) {
return 0;
}
// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时，才会选取对应子节点
int leftGain = max(maxGain(node->left), 0);
int rightGain = max(maxGain(node->right), 0);
// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node->val + leftGain + rightGain;
// 更新答案
maxSum = max(maxSum, priceNewpath);
// 返回节点的最大贡献值
return node->val + max(leftGain, rightGain);
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
};
剑指 Offer II 052. 展平二叉搜索树
给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
中序遍历展平
方法一：中序遍历存到数组中，根据数组重建二叉树
中序遍历得到的数组，数组里里面的次序就是二叉树的次序
代码
class Solution {
public:
void inorder(TreeNode *node, vector<int> &res) {
if (node == nullptr) {
return;
}
inorder(node->left, res);
res.push_back(node->val);
inorder(node->right, res);
}
TreeNode *increasingBST(TreeNode *root) {
vector<int> res;
inorder(root, res);
TreeNode *dummyNode = new TreeNode(-1);
TreeNode *currNode = dummyNode;
for (int value : res) {
currNode->right = new TreeNode(value);
currNode = currNode->right;
}
return dummyNode->right;
}
};
方法二：使用一个全局变量存储临时根节点，在中序遍历中改变指针指向
代码
class Solution {
private:
TreeNode *resNode;
public:
void inorder(TreeNode *node) {
if (node == nullptr) {
return;
}
inorder(node->left);
// 在中序遍历的过程中修改节点指向
resNode->right = node;
node->left = nullptr;
resNode = node;
inorder(node->right);
}
TreeNode *increasingBST(TreeNode *root) {
TreeNode *dummyNode = new TreeNode(-1);
resNode = dummyNode;
inorder(root);
return dummyNode->right;
}
};
剑指 Offer II 053. 二叉搜索树中的中序后继
给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。
节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。
输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。
题目意思，给个树，给个树上的节点，找到中序遍历的当前节点的下一个节点。
方法一：递归维护前一个节点，如果前一个节点是p，那么当前节点就是目标
维护前节点，使用递归进行中序遍历，在中序遍历的左遍历时，如果前节点是p，那么就让left=当前节点，因为已经找到了，还要进行右子树遍历，那么还是要更新下前电点的值，不让右遍历再次找到。
最后如果左节点不为空，那就是目标，如果右节点不为空，那就是目标。
方法二：用栈模拟递归
思路还是维护pre指针，如果pre是p，那么当前节点就是目标
剑指 Offer II 054. 所有大于等于节点的值之和
给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
题目描述：给的是二叉搜索树，某个节点的左子树都小于这个节点，节点的右子树都大于这个节点。
然后题目想把该节点的左子树包含自己全加起来替换当前节点的值
方法一：反向中序遍历：右中左
右遍历得到的就是从下面加上来的数，再中进行处理
代码
class Solution {
public:
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if (root != nullptr) {
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
}
return root;
}
};
方法二：Morris 遍历
剑指 Offer II 055. 二叉搜索树迭代器
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
题目描述：中序遍历二叉树，BSTIterator初始化类的对象（没有用）next()返回中序遍历的下一个节点的值，hashnext()判断是否还有下一个节点
方法一：迭代
next没必要获得所有元素，如果树很大就会占内存
用一个cur表示当前节点的运行位置，用一个栈来进行迭代。但是左中右，在完成"中"进入右节点后（即上次next函数执行完成后），右节点要一直往左下方走，所以下面上来就一直往下走，然后就是中，中就是目标，然后将指针指向右节点。
方法二：中序遍历将得来的值保存到数组中
代码
class BSTIterator {
private:
void inorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorder(root, res);
return res;
}
vector<int> arr;
int idx;
public:
BSTIterator(TreeNode* root): idx(0), arr(inorderTraversal(root)) {
}
int next() {
return arr[idx++];
}
bool hasNext() {
return (idx < arr.size());
}
};
剑指 Offer II 056. 二叉搜索树中两个节点之和
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12
方法一：遍历二叉树，将值存储到哈希表中
遍历到某个节点时，判断哈希表中是否存在目标值-当前值
方法二：广度(层次)遍历插入到哈希表
方法三：遍历二叉树，将节点值保存到数组中，再用双指针
由于搜索树中序遍历带有次序
智能推荐
5个超厉害的资源搜索网站，每一款都可以让你的资源满满！_最全资源搜索引擎-程序员宅基地
文章浏览阅读1.6w次，点赞8次，收藏41次。生活中我们无时不刻不都要在网站搜索资源，但就是缺少一个趁手的资源搜索网站，如果有一个比较好的资源搜索网站可以帮助我们节省一大半时间！今天小编在这里为大家分享5款超厉害的资源搜索网站，每一款都可以让你的资源丰富精彩！网盘传奇一款最有效的网盘资源搜索网站你还在为找网站里面的资源而烦恼找不到什么合适的工具而烦恼吗？这款网站传奇网站汇聚了4853w个资源，并且它每一天都会持续更新资源；..._最全资源搜索引擎
Book类的设计(Java)_6-1 book类的设计java-程序员宅基地
文章浏览阅读4.5k次，点赞5次，收藏18次。阅读测试程序，设计一个Book类。函数接口定义：class Book{}该类有 四个私有属性 分别是 书籍名称、 价格、 作者、 出版年份，以及相应的set 与get方法；该类有一个含有四个参数的构造方法，这四个参数依次是 书籍名称、 价格、 作者、 出版年份 。裁判测试程序样例：import java.util.*;public class Main { public static void main(String[] args) { List <Book>_6-1 book类的设计java
基于微信小程序的校园导航小程序设计与实现_校园导航微信小程序系统的设计与实现-程序员宅基地
文章浏览阅读613次，点赞28次，收藏27次。相比于以前的传统手工管理方式，智能化的管理方式可以大幅降低学校的运营人员成本，实现了校园导航的标准化、制度化、程序化的管理，有效地防止了校园导航的随意管理，提高了信息的处理速度和精确度，能够及时、准确地查询和修正建筑速看等信息。课题主要采用微信小程序、SpringBoot架构技术，前端以小程序页面呈现给学生，结合后台java语言使页面更加完善，后台使用MySQL数据库进行数据存储。微信小程序主要包括学生信息、校园简介、建筑速看、系统信息等功能，从而实现智能化的管理方式，提高工作效率。
有状态和无状态登录
传统上用户登陆状态会以 Session 的形式保存在服务器上，而 Session ID 则保存在前端的 Cookie 中；而使用 JWT 以后，用户的认证信息将会以 Token 的形式保存在前端，服务器不需要保存任何的用户状态，这也就是为什么 JWT 被称为无状态登陆的原因，无状态登陆最大的优势就是完美支持分布式部署，可以使用一个 Token 发送给不同的服务器，而所有的服务器都会返回同样的结果。有状态和无状态最大的区别就是服务端会不会保存客户端的信息。
九大角度全方位对比Android、iOS开发_ios 开发角度-程序员宅基地
文章浏览阅读784次。发表于10小时前| 2674次阅读| 来源TechCrunch| 19 条评论| 作者Jon EvansiOSAndroid应用开发产品编程语言JavaObjective-C摘要：即便Android市场份额已经超过80%，对于开发者来说，使用哪一个平台做开发仍然很难选择。本文从开发环境、配置、UX设计、语言、API、网络、分享、碎片化、发布等九个方面把Android和iOS_ios 开发角度
搜索引擎的发展历史
搜索引擎的发展历史可以追溯到20世纪90年代初，随着互联网的快速发展和信息量的急剧增加，人们开始感受到了获取和管理信息的挑战。这些阶段展示了搜索引擎在技术和商业模式上的不断演进，以满足用户对信息获取的不断增长的需求。
随便推点
控制对象的特性_控制对象特性-程序员宅基地
文章浏览阅读990次。对象特性是指控制对象的输出参数和输入参数之间的相互作用规律。放大系数K描述控制对象特性的静态特性参数。它的意义是：输出量的变化量和输入量的变化量之比。时间常数T当输入量发生变化后，所引起输出量变化的快慢。（动态参数） ..._控制对象特性
FRP搭建内网穿透(亲测有效)_locyanfrp-程序员宅基地
文章浏览阅读5.7w次，点赞50次，收藏276次。FRP搭建内网穿透1.概述：frp可以通过有公网IP的的服务器将内网的主机暴露给互联网，从而实现通过外网能直接访问到内网主机；frp有服务端和客户端，服务端需要装在有公网ip的服务器上，客户端装在内网主机上。2.简单的图解：3.准备工作：1.一个域名（www.test.xyz）2.一台有公网IP的服务器(阿里云、腾讯云等都行)3.一台内网主机4.下载frp，选择适合的版本下载解压如下：我这里服务器端和客户端都放在了/usr/local/frp/目录下4.执行命令# 服务器端给执_locyanfrp
UVA 12534 - Binary Matrix 2 (网络流‘最小费用最大流’ZKW)_uva12534-程序员宅基地
文章浏览阅读687次。题目：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=93745#problem/A题意：给出r*c的01矩阵，可以翻转格子使得0表成1,1变成0，求出最小的步数使得每一行中1的个数相等，每一列中1的个数相等。思路：网络流。容量可以保证每一行和每一列的1的个数相等，费用可以算出最小步数。行向列建边，如果该格子是_uva12534
免费SSL证书_csdn alphassl免费申请-程序员宅基地
文章浏览阅读504次。1、Let's Encrypt 90天，支持泛域名2、Buypass：https://www.buypass.com/ssl/resources/go-ssl-technical-specification6个月，单域名3、AlwaysOnSLL：https://alwaysonssl.com/ 1年，单域名 可参考蜗牛（wn789）4、TrustAsia5、Alpha..._csdn alphassl免费申请
测试算法的性能（以选择排序为例）_算法性能测试-程序员宅基地
文章浏览阅读1.6k次。测试算法的性能 很多时候我们需要对算法的性能进行测试，最简单的方式是看算法在特定的数据集上的执行时间，简单的测试算法性能的函数实现见testSort()。【思想】：用clock_t计算某排序算法所需的时间，（endTime - startTime）/ CLOCKS_PER_SEC来表示执行了多少秒。【关于宏CLOCKS_PER_SEC】：以下摘自百度百科，“CLOCKS_PE_算法性能测试
Lane Detection_lanedetectionlite-程序员宅基地
文章浏览阅读1.2k次。fromhttps://towardsdatascience.com/finding-lane-lines-simple-pipeline-for-lane-detection-d02b62e7572bIdentifying lanes of the road is very common task that human driver performs. This is important ..._lanedetectionlite