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

/*
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* root) {
        deque<pair<TreeNode*, int>> Node;
        vector<vector<int>> order;
        Node.push_front(make_pair(root, 0));
        for (int h = 0; !Node.empty(); h++) {
            vector<int> layer;
            if (h % 2 == 0) {
                while (!Node.empty() && Node.front().second == h) {
                    root = Node.front().first;
                    Node.pop_front();
                    if (root != nullptr) {
                        layer.push_back(root->val);
                        Node.push_back(make_pair(root->left, h + 1));
                        Node.push_back(make_pair(root->right, h + 1));
                    }
                }
            } else {
                while (!Node.empty() && Node.back().second == h) {
                    root = Node.back().first;
                    Node.pop_back();
                    if (root != nullptr) {
                        layer.push_back(root->val);
                        Node.push_front(make_pair(root->right, h + 1));
                        Node.push_front(make_pair(root->left, h + 1));
                    }
                }
            }
            if (!layer.empty())
                order.push_back(layer);
        }
        return order;
    }

};

这个题是总结规律总结出来的。主要是考虑遍历当前层结点存入当前层孩子的顺序和下一次取出的顺序。我一开始觉得每一层按照奇数偶数层区分当前遍历父母时先遍历左还是先遍历右，下一层从栈顶到栈底就ok了。但是如果只是用一个栈，就会出现，下一层的结点压入了这一层还没有遍历到的结点上面，导致这一层剩下的结点取不出来的问题。一个解决思路就是每一层遍历自己结点和存孩子结点用不同的栈。还有一个思路就是使用双边队列。下面是我总结的规律：

如果是偶数层（根结点是0层），遍历这一层的结点从队列头依次取出，存孩子结点先存左孩子，再存右孩子，从队尾依次往里压。

如果是奇数层，遍历这一层的结点从队列尾依次取出，存孩子结点先存右孩子，再存左孩子，从队头依次往里压。