题解 | #按之字形顺序打印二叉树#

/*
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) {
        if(pRoot==nullptr)
            return vector<vector<int> >();


        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        TreeNode* bt;
        //放入第一层
        s1.push(pRoot);



        vector<vector<int> > res;
        vector<int> temp;


        int i=0;
        while(s1.empty()!=1||s2.empty()!=1)
        {
            //遍历奇数层
            while(s1.empty()!=1)
            {
                bt=s1.top();
                s1.pop();

                temp.push_back(bt->val);

                //奇数层的子叶结点加入偶数层
                if(bt->left!=nullptr)
                    s2.push(bt->left); 
                if(bt->right!=nullptr)
                    s2.push(bt->right); 

            }
            if(temp.empty()!=1)
                res.push_back(temp);
            temp.clear();

            //遍历偶数层
            while(s2.empty()!=1)
            {
                bt=s2.top();
                s2.pop();

                temp.push_back(bt->val);

                //奇数层的子叶结点加入偶数层，注意要先加右再加左才是完全相反的
                if(bt->right!=nullptr)
                    s1.push(bt->right); 
                if(bt->left!=nullptr)
                    s1.push(bt->left); 
            }

            if(temp.empty()!=1)
                res.push_back(temp);
            temp.clear();

        }

        return res;
        
    }
    
};

大体上的思路是将层序遍历中的队列换为栈，并作一些小调整即可实现