南通物流网站建设,网站建设论文的中期报告,免费的个人主页空间,天元建设集团有限公司青岛分公司张德平不干了本专栏内容为#xff1a;算法学习专栏#xff0c;分为优选算法专栏#xff0c;贪心算法专栏#xff0c;动态规划专栏以及递归#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习#xff0c;你可以了解并掌握算法。 #x1f493;博主csdn个人主页#xff1a;小… 本专栏内容为算法学习专栏分为优选算法专栏贪心算法专栏动态规划专栏以及递归搜索与回溯算法专栏四部分。 通过本专栏的深入学习你可以了解并掌握算法。 博主csdn个人主页小小unicorn ⏩专栏分类算法从入门到精通 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 专题十三 N叉树的层序遍历算法原理 二叉树的锯齿形层序遍历算法原理 在每个树行中找最大值算法原理 N叉树的层序遍历
给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。
树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例
算法原理
层序遍历很简单本题要返回一个数组我们要在遍历的同时设置一个变量用来计数统计队列里面有多少元素有几个就出队几个每出去一个就把对应的孩子弄进去 代码实现
/*
// 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(rootnullptr)return ret;q.push(root);while(q.size()){int szq.size();//先求出本层需要元素的个数vectorint tmp;//统计本层的节点for(int i0;isz;i){Node*tq.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;}
};二叉树的锯齿形层序遍历
给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。
算法原理
锯齿形类似于S型本题是根据S型来输出结果。 其实本题也不难 既然你是S型。那么我们在层序遍历的同时增加一个标记位。 当遍历到偶数层就给他逆序一下奇数不用变即可。 代码实现
/*** 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(rootnullptr)return ret;queueTreeNode*q;q.push(root);int level1;while(q.size()){int szq.size();vectorint tmp;for(int i0;isz;i){auto tq.front();q.pop();tmp.push_back(t-val);if(t-left) q.push(t-left);if(t-right) q.push(t-right);}//判断是否逆序if(level %2 0)reverse(tmp.begin(),tmp.end());ret.push_back(tmp);level;}return ret;}
};在每个树行中找最大值
给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。
算法原理
本题很简单利用层序遍历统计每一层的最大值即可。 代码实现
/*** 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(rootnullptr)return ret;queueTreeNode*q;q.push(root);while(q.size()){int szq.size();int tmpINT_MIN;for(int i0;isz;i){auto tq.front();q.pop();tmpmax(tmp,t-val);if(t-left)q.push(t-left);if(t-right) q.push(t-right);}ret.push_back(tmp);}return ret;}
};
