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

该题类似于二叉树的层序遍历，间隔一层就会出现翻转的情况而已。

/*
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> > rst;
        if(pRoot == NULL)
            return rst;

        vector<TreeNode*> node_stack;
        node_stack.push_back(pRoot);

        int depth = 1;
        while(node_stack.size())
        {
            vector<int> value;
            vector<TreeNode*> node_next;

            //先将下一层的结点统计出来;
            for(auto& node: node_stack)
            {
                if(node->left)
                        node_next.push_back(node->left);
                if(node->right)
                        node_next.push_back(node->right);
            }

            //如果是偶数层，则翻转vector;
            if(depth%2 == 0)
            {
                reverse(node_stack.begin(), node_stack.end());
            }
            //获取当前层的val;
            for(auto& node: node_stack)
            {
                value.push_back(node->val);
            }

            rst.push_back(value);
            node_stack = node_next;
            depth++;
        }
        return rst;
    }

};