PigyChan_LeetCode 103. 二叉树的锯齿形层次遍历_综合

二叉树的锯齿形层次遍历难度中等

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

例如：
给定二叉树 [3,9,20,null,null,15,7],
在这里插入图片描述

返回锯齿形层次遍历如下：
在这里插入图片描述

思路1.0：

层次遍历，队列走起

代码1.0（已完成）：

class Solution {
    public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if (root == NULL) return vector<vector<int>>();vector<vector<int>> rst;queue<TreeNode*> que;int layers = 0;       //记录层数奇偶que.push(root);while (!que.empty()){
    vector<int> thisLayer;          //存储该层结果++layers;                       //层数+1int len = que.size();           //处理该层所有节点for (int i = 0; i < len; ++i){
    if (que.front()->left != NULL) que.push(que.front()->left);if (que.front()->right != NULL) que.push(que.front()->right);//如果是偶数层，从右往左插入if (layers % 2 == 0){
    thisLayer.insert(thisLayer.begin(), que.front()->val);}//如果是奇数层，从左往右插入else if(layers%2!=0){
    thisLayer.push_back(que.front()->val);}//该节点处理完毕que.pop();}//该层处理完毕rst.push_back(thisLayer);}return rst;}};

跟层次遍历有关的问题，用队列就完事儿了。
在这里插入图片描述