《剑指offer刷题笔记》33、之字形打印二叉树【c++详细题解】-一一网

【摘要】题目
请实现一个函数按照之字形顺序从上向下打印二叉树。
即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null] 8 / \
12 2 / \ 6 4
输出：[[8],…

题目

请实现一个函数按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null] 8 / \
  12  2 / \ 6   4
输出：[[8], [2, 12], [6, 4]]

  
 
  1
  2
  3
  4
  5
  6
  7

思路

在上一题的基础上加一个标记，奇数行为从左到右，偶数行为从右到左。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public: vector<vector<int>> printFromTopToBottom(TreeNode* root) { vector<vector<int>>res; if(!root) return res; queue<TreeNode*>q; vector<int>level; //记录一层的节点 q.push(root); q.push(NULL);// 一层的结尾标记 bool flag = false; while(q.size()) { auto t = q.front(); q.pop(); if(!t) { if(!level.size()) break; if(flag) reverse(level.begin(),level.end()); res.push_back(level); level.clear(); q.push(NULL); flag = !flag; } else { level.push_back(t->val); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } } return res; }
};

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42