题解 | #之字形打印二叉树#

思路

和按层打印二叉树一样，也是广度优先（队列实现）
注意的是需要指定一个奇偶位置，根据这个奇偶来设置保存的方式（是否reverse）

代码

/*
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) {
        // 广度优先遍历
        queue<TreeNode*> q;
        vector<vector<int> > res;
        if(pRoot==nullptr){
            return  res;
        }

        q.push(pRoot);
        bool even = false;
        while(!q.empty()){
            int len = q.size();
            vector<int> tmp_vec;
            while(len>0){

                // 取值
                auto node = q.front();
                q.pop();
                len--;

                tmp_vec.push_back(node->val);

                // 存放值
                if(node->left!=nullptr){
                    q.push(node->left);
                }
                if(node->right!=nullptr){
                    q.push(node->right);
                }


            }

            if(even){    // 若为偶数 则反转
                reverse(tmp_vec.begin(), tmp_vec.end());
            }
            even = !even;

            res.push_back(tmp_vec);

        }


        return res;
    }

};