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

第十一题 主要思路 利用队列的层序遍历

/*
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> > ans;
        // 边界问题
        if(pRoot == NULL)
            return ans;
        
        // 用于层次遍历
        queue<TreeNode *> p;
        // 第一次先把根节点放进去
        p.push(pRoot);
        // 记录层数 因为每个246...层都要反转结果
        int level=0;
        
        // 层次遍历 如果队列不是空，则继续往下遍历
        while( !p.empty() ){
            // 就在这一层存有几个 决定了之后要遍历的次数
            int length = p.size();
            
            // 保存所在层的结果 是一个一维数组(容器)
            // 最后插入到要返回的大的二维数组(容器)中
            vector<int> temp;
            // 每一层 有几个就会遍历几次
            // 假设 树长这样1-23-#456-##789#
            // 则对应的每一层遍历的次数为 1-2-3-3
            
            // length 的统计使得上一层的结点全部访问，队列中剩下的全是新入队列的 下一层的结点
            while(length--)
            {
                // 保存一下这个结点 下面两行相当于学数据结构中单个pop的功能
                // 因为在c++库函数里 他的访问该节点 和 弹出该节点是分为两步的 先访问，再弹出
                TreeNode* thisnode = p.front();
                p.pop();
                
                // 把该节点的数据暂存下来
                temp.push_back(thisnode->val);
                
                // 如果左右孩子还有 就push进队列（记住，此时所有入得队列 都代表是下一层的）
                if(thisnode->left!=NULL)
                    p.push(thisnode->left);
                if(thisnode->right!=NULL)
                    p.push(thisnode->right);
            }
            
            // 记录一下当前的层数，每到到偶数层 都要反转
            level++;
            if(level%2==0)
                reverse(temp.begin(),temp.end());
            
            // 保存好本层的结果
            ans.push_back(temp);
        }
        return ans;
    }
    
};