每天一道leetcode：剑指 Offer 32 - III. 从上到下打印二叉树 III（中等广度优先遍历）

今日份题目：

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

示例

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

返回其层次遍历结果：
[
  [3],
  [20,9],
  [15,7]
]

提示

1. 节点总数 <= 1000

题目思路

使用广度优先遍历，与II不同之处在于，需要对偶数行的内容进行翻转。这里用到了c++库中的reverse函数进行vector的int型内容的翻转。

reverse ( v.begin( ) , v.end ( ) )

代码

/*** 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>> levelOrder(TreeNode* root) {vector<vector<int> > ans;if(root==NULL) return {};queue<TreeNode*> p;//BFSp.push(root);int flag=0;while(!p.empty()){int n=p.size();ans.push_back(vector<int> ());for(int i=0;i<n;i++){TreeNode* cur=p.front();p.pop();ans.back().push_back(cur->val);if(cur->left) p.push(cur->left);if(cur->right) p.push(cur->right);} }for(int i=1;i<ans.size();i+=2) reverse(ans[i].begin(),ans[i].end());return ans;}
};

提交结果

 欢迎大家在评论区讨论，如有不懂的代码部分，欢迎在评论区留言！