首页 > 剑指offer:面试题32 - III. 从上到下打印二叉树 III

剑指offer:面试题32 - III. 从上到下打印二叉树 III

题目: 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如:

给定二叉树: [3,9,20,null,null,15,7],

    3

   /

  9  20

    /  

   15   7

返回其层次遍历结果:

[

  [3],

  [20,9],

  [15,7]

]

提示:节点总数 <= 1000


解题:使用双端对列deque

奇偶层的打印顺序不一样是相反的,可以利用层数偶数与否调用reverse来解决,但是海量数据时这个效率很低,不推荐。因为奇数层的打印顺序是从左到右,偶数层的打印顺序是从右到左,可以利用STL容器deque中push_back(),push_front(),front(),back(),pop(),popfront()来实现

前取后放,后取前放

class Solution {
public:vector> levelOrder(TreeNode* root) {vector> res;if (root==NULL)return res;bool flag = true; //从左向右打印为true,从右向左打印为falsedeque q;q.push_back(root);while (!q.empty()){int n = q.size();vector out;TreeNode* node;while (n>0){if (flag) // 前取后放:从左向右打印,所以从前边取,后边放入{node = q.front();q.pop_front();if (node->left)q.push_back(node->left);  // 下一层顺序存放至尾if (node->right)q.push_back(node->right);}else  //后取前放: 从右向左,从后边取,前边放入{node = q.back();q.pop_back();if (node->right)q.push_front(node->right);  // 下一层逆序存放至首if (node->left)q.push_front(node->left);}out.push_back(node->val);n--;}flag = !flag;res.push_back(out);}return res;}
};

 

更多相关:

  • C语言中打印‘%’不能直接printf("%"),这里的'%'有特殊含义的,要想打印的话,需要输入printf("%%"),两个'%'才可以将它打印出来。C语言中的其他的特殊字符,以后再慢慢做整理。...

  •   使用DevExpress.XtraReports打印报表时,分别采用两种打印方式。以下面的打印样式为列作简要说明:   第一种:表头表尾保持不变,表中数据根据实际打印条数更改。如现在我要打印的学生为三个,则得到如下的报表: 实现方式:1、新建在XtraReport1中,分别在PageHeader中设计表头,在Detail中设计表...

  • 在做B/S项目开发时。难免会遇到网页打印问题! 可以用css控制, @media print .a {display:block} .b {display:hidden} 好像是这样。把你不想打印的部分class设为b 首先在网页中添加:      
  • web.xml 的加载顺序是:context-param -> listener -> filter -> servlet 。 过滤器执行顺序是根据filter-mapping ,不是根据filter顺序。 转载于:https://www.cnblogs.com/xiongjinpeng/p/web-xml%e9%85%8d%e7...