按之字型顺序打印二叉树

图解:

链接

思路:

由于对于二叉树的分层打印,一般用队列进行维护

但是由于现在是按照之字形的顺序进行打印的,所以有些层需要在原先的顺序上进行反转

1.先判断树是否为空,如果为空,就直接返回

2.否则就创建一个队列进行维护

3.将每一层的节点都插入队列中,再将每一层的节点出队列

4.每一层的节点出队列的时候,需要将出队列的点存入一个一维数组中,并扩展其子节点,将子节点插入队列中

5.再去判断该层的节点是否遍历顺序是从右往左,如果是,就需要进行反转后插入二维数组中

代码:

class Solution {
public:
//由于要将树进行之字形打印后存在二维数组中返回
//对于树的分层打印,一般用队列进行维护
//但是对于之子型的打印方式,每隔一层就需要更改遍历方向
//因此可以先用队列进行维护(正常的从左到右的顺序存每层树的节点),之后再将需要进行反转的层的节点进行反转
    vector<vector<int> > Print(TreeNode* pRoot) {
        //定义一个二维数组进行存之字形打印树的节点
        vector<vector<int>>res;
        TreeNode* head=pRoot;
        //先判断一下树是否为空,如果是空树,就不需要进行打印,直接返回
        if(pRoot==NULL){
            return res;
        }
        //否则需要创建一个队列进行维护
        queue<TreeNode*>q;
        //先将根节点入队列
        q.push(head);
        //标记变量,标记每层是否需要反转
        bool flag=true;
        //只要队列不为空,即还有点没有进行扩展,就继续
        while(!q.empty()){
            //对于每一层的树节点,用一个一维数组存
            vector<int>now;
            //获得队列的长度即等于该层树的节点的个数
            int size=q.size();
            flag=!flag;
            //将该层的每个节点都进行扩展,将子节点插入队列中
            //再将该节点出队列,将出队列的点都放入容器now中
            for(int i=0;i<size;i++){
                TreeNode* t=q.front();
                q.pop();
                now.push_back(t->val);
                if(t->left){
                    q.push(t->left);
                }
                if(t->right){
                    q.push(t->right);
                }
            }
            //再判断一下该行是否遍历方向是从右往左,如果是,就需要进行反转后再将数组放入二维的res中
            if(flag){
                reverse(now.begin(),now.end());
            }
            res.push_back(now);

        }
        return res;

    }
};