剑指offer:77-题解 | #按之字形顺序打印二叉树#

按之字形顺序打印二叉树

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

题目描述


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

数据范围:15000≤n≤1500,树上每个节点的val满足 |val| <= 100∣val∣<=100
要求:空间复杂度:O(n),时间复杂度:O(n)
例如: 给定的二叉树是{1,2,3,#,#,4,5}
alt
该二叉树之字形层序遍历的结果是 [ [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;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
06-05 15:27
点赞 评论 收藏
分享
04-17 10:16
门头沟学院 Java
小浪_coder:24届很难找了,马上25的都毕业了还有很多没找到的
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务