之字形打印二叉树

之字形打印二叉树，可以使用两个栈来存储数据，栈1存储奇数层结点数据，栈2存储偶数层计点数据。奇数层从左到右打印，即栈1出栈，栈2按先左孩子，后右孩子入栈；偶数层从右往左打印，即栈1出栈，栈2按先右孩子，后左孩子入栈。

/*
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>> vec;
        vector<int> v;
        if(pRoot == nullptr){
            return vec;
        }
        //奇数层，从右到左入栈，从左到右输出
        stack<TreeNode*> l_stack;
        //偶数层，从左到右入栈，从右到左输出
        stack<TreeNode*> r_stack;
        TreeNode* pNode = pRoot;
        l_stack.push(pNode);
        while(!l_stack.empty() || !r_stack.empty()){
            while(!l_stack.empty()){
                pNode = l_stack.top();
                v.push_back(pNode->val);
                l_stack.pop();
                if(pNode->left != nullptr){
                    r_stack.push(pNode->left);                    
                }
                if(pNode->right != nullptr){
                    r_stack.push(pNode->right);
                }
            }
            if(!v.empty()){
                vec.push_back(v);
                v.clear();
            }           

            while(!r_stack.empty()){
                pNode = r_stack.top();
                v.push_back(pNode->val);
                r_stack.pop();
                if(pNode->right != nullptr){
                    l_stack.push(pNode->right);
                }
                if(pNode->left != nullptr){
                    l_stack.push(pNode->left);                    
                }
            }
            if(!v.empty()){
                vec.push_back(v);
                v.clear();
            }     
        }
        return vec;
    }

};