题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：15000≤n≤1500,树上每个节点的val满足 |val| <= 100∣val∣<=100
要求：空间复杂度：O(n)，时间复杂度：O(n)
例如： 给定的二叉树是{1,2,3,#,#,4,5}

该二叉树之字形层序遍历的结果是 [ [1], [3,2], [4,5] ]

题解1：使用队列+双向队列

代码

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
      //题解1：不好理解的代码，未优化
//         vector<vector<int>> result;
//         if(!pRoot) return result;
//         queue<TreeNode*> qu;//使用队列
//         qu.push(pRoot);//根节点入栈
//         bool oddOreven = true;//设置奇偶层，奇数层为true
//         while(!qu.empty()){
//             vector<int> de;//存放每行结果的双向队列
//             int size = qu.size();//保存队列中元素个数
//             //将队列中的元素全部拿出
//             for(int i =0;i<size;i++){
//                 TreeNode * temp = qu.front();
//                 qu.pop();
//                 if(!temp) continue;
//                 //将每个节点的左右节点按照从左到右的顺序入队列
//                 qu.push(temp->left);
//                 qu.push(temp->right);
//                 //将元素插入数组中
//                 de.push_back(temp->val);
//             }
//             if(oddOreven == false)//偶数层
//                 reverse(de.begin(), de.end());
//             //取出队列中的元素
//             if(!de.empty()){ //如果为空，跳过
//                 result.push_back(de);
//             }
//             //下次循环层数变为偶数
//             oddOreven = oddOreven == true? false:true;
//         }
//         return result;
        //以下代码更加好理解，优化代码
        vector<vector<int>> v;
        queue<TreeNode*> q;//层次遍历用的队列
        bool b = 0;//b=0作为二叉树奇数层
        if(!pRoot) return {};
        q.push(pRoot);
        while(!q.empty()){
            vector<int> arr;
         //注意：这里的size在循环体中不能改变，所以这里不能直接使用q.size()
         //目的：为了求出每层由多少结点
            int size = q.size(); //二叉树每层具有多少个元素
            for(int i =0;i<size;i++){
                TreeNode * temp = q.front();
                q.pop();
                //将该层结点的子节点全部入队列
                if(temp->left)
                    q.push(temp->left);
                if(temp->right)
                    q.push(temp->right);
                //将该层的结点入数组中
                arr.push_back(temp->val);
            }
            //判断是奇数层还是偶数层
            if(b){ // 偶数层，则数组反序，然后将之存放如数组v中
                reverse(arr.begin(), arr.end());
                v.push_back(arr);
                b = 0;//偶数层之后必然是奇数层
            }else{
                v.push_back(arr);
                b = 1;//奇数层之后必然是偶数层
            }
        }
        return v;
    }
};