建设网站最重要的是什么意思,东莞网站建设+旅游,wordpress分类编辑器,遵义网站制作报价文章目录 N 叉数的层序遍历二叉树的锯齿形层序遍历二叉树最大宽度在每个树行中找最大值 BFS是图上最基础、最重要的搜索算法之一#xff1b; 每次都尝试访问同一层的节点如果同一层都访问完了#xff0c;再访问下一层 BFS基本框架
void bfs(起始点)
{将起始点放入队列中;标记… 文章目录 N 叉数的层序遍历二叉树的锯齿形层序遍历二叉树最大宽度在每个树行中找最大值 BFS是图上最基础、最重要的搜索算法之一 每次都尝试访问同一层的节点如果同一层都访问完了再访问下一层 BFS基本框架
void bfs(起始点)
{将起始点放入队列中;标记起点已访问;while(队列不为空){访问队列中首元素;删除队首元素;for(队首元素所有相邻点){if(该点未被访问过且合法)将该点加入队列末尾; }}宽搜结束;
} N 叉数的层序遍历 题目N 叉数的层序遍历 思路
BFS宽搜创建vectorvectorint ret来保存结果创建queueNode* q来将根节点入队如果根节点为空则直接返回空的ret当队列不为空的时候一直循环 获取当前队列大小 用vectorint tmp来统计本层节点 出队头元素保存在tmp中若其孩子节点非空则进入队列 每层节点出队后将其保存在tmp中的节点push_back进ret
C代码
/*
// Definition for a Node.
class Node {
public:int val;vectorNode* children;Node() {}Node(int _val) {val _val;}Node(int _val, vectorNode* _children) {val _val;children _children;}
};
*/class Solution
{
public:vectorvectorint levelOrder(Node* root) {vectorvectorint ret; // 存储层序遍历的结果queueNode* q; // 层序遍历需要的队列if(root nullptr) return ret;q.push(root);while(q.size()){int n q.size(); // 本层元素个数vectorint tmp; // 统计本层节点for(int i 0; i n; i){Node* t q.front();q.pop();tmp.push_back(t-val);for(Node* child : t-children) // 让下一次节点入队{if(child ! nullptr)q.push(child);}}ret.push_back(tmp);}return ret;}
};二叉树的锯齿形层序遍历 题目二叉树的锯齿形层序遍历 思路1
和上一题的思路一样我们先封装一个函数vectorvectorint levelOrder(TreeNode *root)正常层序遍历该二叉树将其结果存储在vectorvectorint ret再对结果ret进行逆序当为偶数层时对其结果进行逆序
C代码
/*** 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:vectorvectorint zigzagLevelOrder(TreeNode *root){vectorvectorint ret levelOrder(root);// 偶数层时对其结果进行逆序for (int i 1; i ret.size(); i 2)reverse(ret[i].begin(), ret[i].end());return ret;}vectorvectorint levelOrder(TreeNode *root){vectorvectorint ret;if (!root)return ret;queueTreeNode* q;q.push(root);while (q.size()){int n q.size();vectorint tmp;for(int i 0; i n; i){TreeNode* t q.front();tmp.push_back(t-val);q.pop();if(t-left) q.push(t-left);if(t-right) q.push(t-right);}ret.push_back(tmp);}return ret;}
};思路2 我们也可以添加一个标记位flag当奇数层时正常添加到结果数组偶数层时逆序后进入结果数组
C代码
/*** 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:vectorvectorint zigzagLevelOrder(TreeNode *root){vectorvectorint ret;if (!root)return ret;queueTreeNode* q;q.push(root);int flag 0; // 标志层数while (q.size()){flag;int n q.size();vectorint tmp;for(int i 0; i n; i){TreeNode* t q.front();tmp.push_back(t-val);q.pop();if(t-left) q.push(t-left);if(t-right) q.push(t-right);}if(flag % 2 0) reverse(tmp.begin(), tmp.end()); // 偶数层逆序后再进入结果数组ret.push_back(tmp);}return ret;}};二叉树最大宽度 题目二叉树最大宽度 思路 对于数组存储的二叉树我们知道
父亲节点下标为i从一开始。则左孩子下标为2 * i 左孩子下标为2 * i 1 如果二叉树非常不平衡节点全部在右侧空节点也进行插入操作去计算的话空间是远远不够的 我们可以通过计算每层插入节点的头和尾下标差值并使用vector来模拟队列操作每次都覆盖前一层以防超出内存计算差值使用无符号整型避免数据溢出 定义一个队列 vectorpairTreeNode*, unsigned int q// 数组模拟队列元素包含一个二叉树节点指针和该节点在完全二叉树中的编号将根节点和其对应编号 1 放入队列 q中进入循环获取当前层数收尾元素并且更新当前最大宽度创建一个临时队列tmp来更新q
C代码
/*** 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:int widthOfBinaryTree(TreeNode* root) {vectorpairTreeNode*, unsigned int q; // 数组模拟队列q.push_back({root, 1});unsigned int ret 0;while(q.size()){auto [x1, y1] q[0];auto [x2, y2] q.back();ret max(ret, y2 - y1 1);// 下一层进临时队vectorpairTreeNode*, unsigned int tmp;for(auto [x, y] : q){if(x-left) tmp.push_back({x-left, y * 2});if(x-right) tmp.push_back({x-right, y * 2 1});}q tmp;} return ret;}
};在每个树行中找最大值 题目在每个树行中找最大值 思路 利用层序遍历统计每层最大值 C代码
/*** 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:vectorint largestValues(TreeNode* root) {vectorint ret;if(root nullptr) return ret;queueTreeNode* q;q.push(root);while(q.size()){int n q.size();int _max INT_MIN;for(int i 0; i n; i){auto t q.front();q.pop();_max max(_max, t-val);if(t-left) q.push(t-left);if(t-right) q.push(t-right);}ret.push_back(_max);}return ret;}
};
