[AcWing]45. 之字形打印二叉树

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

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

数据范围

树中节点的数量 [0,1000]。

样例

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

算法思路1、2

在之前的题的基础上，添加了条件判断

详情参考分行从上往下打印二叉树

代码实现1

/**
 * 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>> ans;
        // 空树，返回空集合
        if(!root) return ans;
        
        // 基于BFS的分行操作
        queue<TreeNode *> q;
        q.push(root); // 从根节点开始BFS
        
        // 当前层是否需要逆置
        bool flag = false;
        
        while(q.size()){
            // 下一层的节点数量
            int len = q.size();
            // 保存每层的值
            vector<int> level;
            // 一口气将当前层的节点，全放入队列
            while(len --){
                TreeNode * t = q.front();
                q.pop();
                
                level.push_back(t -> val);
                
                if(t -> left) q.push(t -> left);
                if(t -> right) q.push(t -> right);
            }
            // 逆置判断
            if(flag){
                reverse(level.begin(), level.end());
            }
                
            // 下一层必定与当前层BFS的顺序相反
            flag = !flag;
            // 提交当前层
            ans.push_back(level);
        }
        
        return ans;
    }
};

代码实现2

/**
 * 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>> ans;
        // 空树，返回空集合
        if(!root) return ans;
        
        // 基于BFS的分行操作
        queue<TreeNode *> q;
        q.push(root); // 从根节点开始BFS
        q.push(NULL); // 代表这层结束
        
        // 存储每层的节点值
        vector<int> level;
        
        // 表示是否需要将 level 集合逆置(从右到左)
        bool flag = false;
        
        while(q.size()){
            TreeNode * t = q.front();
            q.pop();
            
            // 如果当前层结束了
            if(!t){
                // 如果下一层没有节点了
                // 比如：4 NULL，while循环拿出4，放入level之后，取出NULL，进入这个if条件里面
                // level不是空，因此提交 level 到 ans 里面
                // 队列里面剩下的是 NULL，再拿出来，此时判断level，为空，break掉
                // 这也就是下一层没有节点的情况
                if(level.empty()) break;
                // 当前层结束了，下一行还有节点，根据类型提交level，再给下一层增加结束标识符
                // 如果需要逆置
                if(flag){
                    reverse(level.begin(), level.end());
                }
                ans.push_back(level);
                q.push(NULL);
                // 为了下一次，level容器是空的，还需要还原空状态
                level.clear();
                // 下一层必定与当前层BFS的顺序相反
                flag = !flag;
                continue;
            }
            // 当前层没结束,正常BFS
            level.push_back(t -> val);
            if(t -> left) q.push(t -> left);
            if(t -> right) q.push(t -> right);
        }
        
        return ans;
    }
};