JZ59-按之字形打印二叉树

要一层一层的打印二叉树，首先想到的是二叉树的层序遍历，通过队列来实现；又因为要“之”字形打印，所以一个队列肯定不够，得用两个队列，但要想用队列实现就必须要能够从队列的末尾取值，并将值从末尾弹出，但队列没有末尾弹出的接口。这正好是栈的特性，所以最后采用两个栈来实现，于是就写出了如下代码：

/*
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>> res;
    if (pRoot == NULL)
    {
        return res;
    }

    stack<TreeNode*> p, q;
    TreeNode* temp;
    p.push(pRoot);

    while (!p.empty() || !q.empty() )
    {
        vector<int> vec;
        while (!p.empty())
        {
            temp = p.top();
            vec.push_back(temp->val);
            p.pop();
            if (temp->left)
            {
                q.push(temp->left);
            }
            if (temp->right)
            {
                q.push(temp->right);
            }
        }
        if (vec.size() != 0)
        {
            res.push_back(vec);
        }
        vec.clear();

        while (!q.empty())
        {
            temp = q.top();
            vec.push_back(temp->val);
            q.pop();
            if (temp->right)
            {
                p.push(temp->right);
            }
            if (temp->left)
            {
                p.push(temp->left);
            }
        }
        if (vec.size() != 0)
        {
            res.push_back(vec);
        }
    }
    return res;
    }

};