按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路

层次遍历，数据隔行反转添加进结果

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        //用来保存最终结果
        vector<vector<int>>result;
        //存储层次遍历一层的数据
        vector<int>data;
        //层次遍历存储一层的结点
        vector<TreeNode*> row;
        //保存下一层的结点
        vector<TreeNode*>tmp;
        /*
        flag==true时，直接存储每一行的数据，
        flag==flag时，倒序存储每一行的数据。
        */
        bool flag = true;
        row.push_back(pRoot);
        if (pRoot==NULL) {
            return result;
        }
        while (!row.empty())
        {
            data.push_back(row[0]->val);
            if (row[0]->left != NULL) {
                tmp.push_back(row[0]->left);
            }
            if (row[0]->right != NULL) {
                tmp.push_back(row[0]->right);
            }
            //没遍历一层，删除一层的数据
            row.erase(row.begin());
            if (row.empty()) {
                row.assign(tmp.begin(),tmp.end());
                tmp.clear();
                if (flag == false) {
                    //翻转vector中的数据
                    reverse(data.begin(),data.end());
                }
                result.push_back(data);
                //标志位置反
                flag = !flag;
                data.clear();
            }
        }
        return result;
    }

};