每天一道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;
        //BFS
        p.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;
    }
};