题目描述

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

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

样例

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

算法1

(树的层次遍历) $O(n)$

• 按层次遍历 得到每一层从左到右排列的结果res(类似 44. 分行从上往下打印二叉树)
• 遍历res根据所在层序号的奇偶性决定是否把序列反转(例如第1层不反转，第2层反转，第3层不反转…)

C++ 代码

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {

            vector<vector<int>> res;
            if(!root) return res;

            queue<TreeNode *> que;
            que.push(root);
            vector<int> part;
            int precnt=1;
            int nextcnt=0;
            while(!que.empty()){
                auto cur=que.front();
                que.pop();
                precnt--;
                part.push_back(cur->val);

                if(cur->left){
                    que.push(cur->left);
                    nextcnt++;
                }


                if(cur->right){
                    que.push(cur->right);
                    nextcnt++;
                }

                if(precnt==0){
                    precnt=nextcnt;
                    nextcnt=0;
                    res.push_back(part);
                    part.clear();
                }

            }

            for(int i=0;i<res.size();i++){
                if(i&1==1){
                    reverse(res[i].begin(),res[i].end());
                }
            }

        return res;


    }
};