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

/*
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; // 创建返回结果的二维数组
        deque<TreeNode*> deq;   // 创建双向队列，保存每层节点
        if(pRoot) deq.push_back(pRoot);     // 如果根节点不为空，将根节点放入队列中
        int flag = 1;   // 标记遍历每层节点的顺序，单数为从前向后，双数为从后向前
        while(!deq.empty()){    // 队列不为空，进入循环
            vector<int> temp_vec;   // 创建临时数组，保存每层节点值
            int size = deq.size();  // 先确定每层循环的次数
            if(flag % 2){   // 如果标记值为单数，则从前向后遍历队列
                for(int i = 0; i < size; ++i){
                    TreeNode* cur = deq.front();    // 队头节点赋给临时节点
                    temp_vec.push_back(cur->val);   // 将临时节点的值加入临时数组中
                    deq.pop_front();    // 删除队头节点
                    if(cur->left) deq.push_back(cur->left);   // 如果临时节点的左孩子不为空，将左孩子加入队列中
                    if(cur->right) deq.push_back(cur->right);   // 如果临时节点的右孩子不为空，将右孩子加入队列中
                }
            }
            else{   // 如果标记值为双数，则从后向前遍历队列
                vector<TreeNode*> temp_node;	// 创建节点数组，保存当前队列中的节点
                for(int i = 0; i < size; ++i){	// 将队列中的节点放入节点数组中
                    temp_node.push_back(deq.front());
                    deq.pop_front();
                }
                for(int i = temp_node.size() - 1; i >= 0; --i){	// 倒叙遍历节点数组，节点值放入临时数组
                    temp_vec.push_back(temp_node[i]->val);
                }
                for(int i = 0; i < temp_node.size(); ++i){	// 将节点数组的左右孩子放入队列中
                    if(temp_node[i]->left) deq.push_back(temp_node[i]->left);
                    if(temp_node[i]->right) deq.push_back(temp_node[i]->right);
                }
            }
            result.push_back(temp_vec);	// 将临时数组加入到结果数组中
            ++flag;	// 每次循环结束之后标记+1
        }
        return result;
    }
};