class Solution 
{
public:
    vector<vector<int> > Print(TreeNode* pRoot) 
    {
        
        TreeNode* cur = pRoot;
        stack<TreeNode*> stack1_LeftToRight;
        stack<TreeNode*> stack2_RightToLeft;
        stack1_LeftToRight.push(pRoot);
        vector<vector<int> > result;
        if (pRoot == NULL)    return result;
        while ((!stack1_LeftToRight.empty()) || (!stack2_RightToLeft.empty()))
        {
            vector<int> re;
            if( (!stack1_LeftToRight.empty()) && (stack2_RightToLeft.empty()))
            {
                while (!stack1_LeftToRight.empty())
                {
                    TreeNode* cur= stack1_LeftToRight.top();
                    if(cur->left!=NULL) stack2_RightToLeft.push(cur->left);
                    if(cur->right!=NULL) stack2_RightToLeft.push(cur->right);
                    re.push_back(cur->val);
                    stack1_LeftToRight.pop();
                }
                result.push_back(re);
            }
            else
            {
                while (!stack2_RightToLeft.empty())
                {
                    TreeNode* cur = stack2_RightToLeft.top();
                    if(cur->right!=NULL) stack1_LeftToRight.push(cur->right);
                    if(cur->left!=NULL) stack1_LeftToRight.push(cur->left);
                    re.push_back(cur->val);
                    stack2_RightToLeft.pop();
                }
                result.push_back(re);    
            }
            re.clear();
        }
        return result;

    }

};