剑指offer 44.分行从上往下打印二叉树 45.之字形打印二叉树

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:
    //这个是分行打印，可以继续用宽搜来做，就是每层结尾要加一个NULL标记。
    //在queue里读取一个数出来之后，先看看是不是NULL，如果是，则把另外创建的数组level的数push_back进答案数组res中，如果不是，则按往常入队
    vector> printFromTopToBottom(TreeNode* root) {
        vector>res;//分行打印，所以为二维数组；
        if(!root ) return res;//仍然判断一下边界条件
        queueq;
        q.push(root);
        q.push(NULL);//每层结尾标识符NULL；
        vectorlevel; //一维数组存储每层的每一个节点
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            if(!t) //如果队头为NULL,说明到了层未
            {
                if(q.size()) q.push(NULL); //此时判断队列是否为空，如果非空，则说明到了到了层末尾，将标识符NULL入队。
                res.push_back(level);//同时将该层level数组push进res数组中，表示一层
                level.clear();//将level数组清空，以便用来表示下一层节点。
            }
            else
            {
                level.push_back(t->val);//如果队头不为空，就按常规宽搜，只不过是讲节点值存储在level数组中。
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
        return res;
    }
};

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> printFromTopToBottom(TreeNode* root) {
        //相比于分行从上往下打印二叉树，只需要加一个Bool变量，bool为TRUE则反转vector数据就行
        vector>res;
        if(!root) return res;
        vectorlevel;
        bool st=false;//加一个bool变量,偶数行则反转数据
        queueq;
        q.push(root);
        q.push(NULL);
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            if(!t)
            {   
                if(level.empty()) break;//向上题那样判断q.size()，也可以。
                q.push(NULL);
                if(st) reverse(level.begin(),level.end());
                st=!st;
                res.push_back(level);
                level.clear();
            }
            else 
            {
                level.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
        return res;
        
    }
};