题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路

创建两个栈分别存放奇数行的数和偶数行的数：
(1)一开始先将根节点放入栈1；
(2)然后开始从栈1中取数，取一个就把它的左、右分别放到栈2里面去，直到它为空；
(3)然后开始从栈2中取数，取一个就把它的右、左分别放到栈1里面去，直到它为空；
(4)重复上面(3)(4)步，直到两个栈全都为空

还是需要注意！！！：只要碰到取左/右的一定要判断一下它的左右是否为空！！！

代码

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        TreeNode* pNode;
        vector<int> res_temp;
        stack<TreeNode*> stack1;//存奇数行的栈
        stack<TreeNode*> stack2;//存偶数行的栈
        stack1.push(pRoot);
        if(pRoot==NULL)
            return res;
        while(!stack1.empty()||!stack2.empty())
        {
            while(!stack1.empty())
            {
                pNode=stack1.top();
                res_temp.push_back(pNode->val);
                if(pNode->left!=NULL)
                    stack2.push(pNode->left);
                if(pNode->right!=NULL)
                    stack2.push(pNode->right);
                stack1.pop();
            }
            if(!res_temp.empty())
                res.push_back(res_temp);
            res_temp.clear();
            while(!stack2.empty())
            {
                pNode=stack2.top();
                res_temp.push_back(pNode->val);
                if(pNode->right!=NULL)
                    stack1.push(pNode->right);
                if(pNode->left!=NULL)
                    stack1.push(pNode->left);
                stack2.pop();
            }
            if(!res_temp.empty())
                res.push_back(res_temp);
            res_temp.clear();
        }
        return res;
    }

};