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

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

        typedef deque<TreeNode*> Deque;
        typedef pair<int, Deque> Pair;
        typedef queue<Pair> Queue;

        Queue notes;
        Deque rootD;
        rootD.push_back(pRoot);
        notes.push(Pair(1, rootD ) );

        while (!notes.empty()) {
            // 记录每层的值
            vector<int> numLayer;
            // 记录每层的节点
            Deque nodeLayer;

            Pair tmp = notes.front();
            notes.pop();

            int layerth = tmp.first;
            size_t length = tmp.second.size();

            if (length == 0)
                break;

            // 奇数层，从左往右
            if (layerth % 2 == 1) {
                for (int i = 0; i < length; i++) {
                    TreeNode* tmpNode = tmp.second.back();
                    tmp.second.pop_back();

                    if (tmpNode->left != nullptr)
                        nodeLayer.push_back(tmpNode->left);
                    if (tmpNode->right != nullptr)
                        nodeLayer.push_back(tmpNode->right);

                    numLayer.push_back(tmpNode->val);
                }
            }
            // 偶数层，从右往左
            else if (layerth % 2 == 0) {
                for (int i = 0; i < length; i++) {
                    TreeNode* tmpNode = tmp.second.back();
                    tmp.second.pop_back();

                    if (tmpNode->right != nullptr)
                        nodeLayer.push_back(tmpNode->right);
                    if (tmpNode->left != nullptr)
                        nodeLayer.push_back(tmpNode->left);

                    numLayer.push_back(tmpNode->val);
                }
            }

            notes.push(Pair(layerth+1, nodeLayer));
            result.push_back(numLayer);
        }

        return result;
    }

};