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

// 树的各种遍历
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> vec;
    vector<vector<int> > v;
    int flag = 1;
    vector<vector<int> > Print(TreeNode* pRoot) {
        if(!pRoot)
            return v;
        zhiPrint(pRoot);
//         v.push_back(vec);
        return v;
    }
    // 建议先看前、中、后序遍历，在看层序遍历，最后看之字遍历

    // 之字遍历
    void zhiPrint(TreeNode* pRoot)
    {
        if(!pRoot)
            return;
        deque<TreeNode*> que;
        que.push_back(pRoot);
        int level = 1;
        while(!que.empty())
        {
            int len = que.size();
            vector<int> vec1;
            while(len--)
            {
                if(level%2)
                {
                    TreeNode* node = que.back();
                    vec1.push_back(node->val);
                    que.pop_back();
                    if(node->left)
                    {
                        que.push_front(node->left);
                    }
                    if(node->right)
                    {
                        que.push_front(node->right);
                    }
                }
                else
                {
                    TreeNode* node = que.front();
                    vec1.push_back(node->val);
                    que.pop_front();
                    if(node->right)
                    {
                        que.push_back(node->right);
                    }
                    if(node->left)
                    {
                        que.push_back(node->left);
                    }
                }
            }
            level++;
            v.push_back(vec1);
            vec1.clear();
        }
    }
    // 前序遍历
    void prePrint(TreeNode* pRoot)
    {
        if(pRoot)
        {
            vec.push_back(pRoot->val);
        }
        if(pRoot->left)
        {
            prePrint(pRoot->left);
        }
        if(pRoot->right)
        {
            prePrint(pRoot->right);
        }
    }
    // 中序遍历
    void midPrint(TreeNode* pRoot)
    {

        if(pRoot->left)
        {
            midPrint(pRoot->left);
        }
        if(pRoot)
        {
            vec.push_back(pRoot->val);
        }
        if(pRoot->right)
        {
            midPrint(pRoot->right);
        }
    }
    // 后序遍历
    void postPrint(TreeNode* pRoot)
    {
        if(pRoot->left)
        {
            postPrint(pRoot->left);
        }
        if(pRoot->right)
        {
            postPrint(pRoot->right);
        }
        if(pRoot)
        {
            vec.push_back(pRoot->val);
        }
    }
    // 层序遍历
    void levelPrint(TreeNode* pRoot)
    {
        queue<TreeNode*> que;
        if(!pRoot)
            return;
        que.push(pRoot);
        while(!que.empty())
        {
            TreeNode* tmp = que.front();
            que.pop();
            vec.push_back(tmp->val);
            if(tmp->left)
                que.push(tmp->left);
            if(tmp->right)
                que.push(tmp->right);
        }
    }
};