N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）
算法原理：
层序遍历很简单，本题要返回一个数组，我们要在遍历的同时设置一个变量用来计数，统计队列里面有多少元素，有几个就出队几个，每出去一个就把对应的孩子弄进去
代码实现：
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: vector<vector<int>> levelOrder(Node* root) { vector<vector<int>> ret;//记录最终结果 queue<Node*> q;//层序遍历需要的队列 if(root==nullptr)return ret; q.push(root); while(q.size()) { int sz=q.size();//先求出本层需要元素的个数 vector<int> tmp;//统计本层的节点 for(int i=0;i<sz;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; } };
二叉树的锯齿形层序遍历
给你二叉树的根节点 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: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> ret; if(root==nullptr)return ret; queue<TreeNode*>q; q.push(root); int level=1; while(q.size()) { int sz=q.size(); vector<int> tmp; for(int i=0;i<sz;i++) { auto t=q.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: vector<int> largestValues(TreeNode* root) { vector<int> ret; if(root==nullptr)return ret; queue<TreeNode*>q; q.push(root); while(q.size()) { int sz=q.size(); int tmp=INT_MIN; for(int i=0;i<sz;i++) { auto t=q.front(); q.pop(); tmp=max(tmp,t->val); if(t->left)q.push(t->left); if(t->right) q.push(t->right); } ret.push_back(tmp); } return ret; } };
