之字形打印二叉树

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

思路：两个栈，用于更换每一层的顺序。每次出栈一个元素再将其子结点压入另一个栈，直至栈空。最终两个栈均空时，全部结点被遍历，程序结束。

解：

 vector<vector<int> > Print(TreeNode* pRoot) {

        vector<int> floor;

        vector<vector<int> > res;

        if (!pRoot) return res;

        stack<TreeNode*> tmp1;

        stack<TreeNode*> tmp2;

        tmp1.push(pRoot);

        int flag=0;

        while (!tmp1.empty() || !tmp2.empty()){

            if (flag==0){

                while (!tmp1.empty()){

                    TreeNode* p=tmp1.top();

                    floor.push_back(p->val);

                    tmp1.pop();

                    if (p->left) tmp2.push(p->left);

                    if (p->right) tmp2.push(p->right);

                }

                flag=1;

                res.push_back(floor);

                floor.clear();

            }

            else{

                while (!tmp2.empty()){

                    TreeNode* p=tmp2.top();

                    floor.push_back(p->val);

                    tmp2.pop();

                    if (p->right) tmp1.push(p->right);

                    if (p->left) tmp1.push(p->left);

                }

                flag=0;

                res.push_back(floor);

                floor.clear();

            }

        }

        return res;

    }