103. 二叉树的锯齿形层序遍历 - 力扣LeetCode103. 二叉树的锯齿形层序遍历 - 给你二叉树的根节点 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返回其节点值的锯齿形层序遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。解题思路本题是在普通二叉树层序遍历基础上增加锯齿反转的要求。使用 BFS 广度优先搜索借助队列完成层序遍历。每次循环开始获取队列大小sz代表当前一层的节点总数循环 sz 次处理整层节点。把当前层节点值存入临时数组同时把左右孩子入队。设置层数标记奇数层正常顺序偶数层反转数组实现锯齿效果。注意边界树为空直接返回空集合。/** * 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%20) reverse(tmp.begin(),tmp.end()); ret.push_back(tmp); level; } return ret; } };