算法日常・每日刷题--＜队列BFS ＞2

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）103. 二叉树的锯齿形层序遍历 - 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 示例 1：[https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg]输入：root = [3,9,20,null,null,15,7]输出：[[3],[20,9],[15,7]]示例 2：输入：root = [1]输出：[[1]]示例 3：输入：root = []输出：[] 提示： * 树中节点数目在范围 [0, 2000] 内 * -100 <= Node.val <= 100https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

题目描述

给你二叉树的根节点root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

解题思路

本题是在普通二叉树层序遍历基础上增加锯齿反转的要求。

1. 使用 BFS 广度优先搜索，借助队列完成层序遍历。
2. 每次循环开始，获取队列大小sz，代表当前一层的节点总数，循环 sz 次处理整层节点。
3. 把当前层节点值存入临时数组，同时把左右孩子入队。
4. 设置层数标记：奇数层正常顺序，偶数层反转数组，实现锯齿效果。
5. 注意边界：树为空直接返回空集合。

/** * 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; } };