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

• 本质BFS，可以使用递归实现，使用vector保存每一层的nodes。
• 但需要注意之字形相邻层顺序相反，所以用一个标志位实现。
• 另外，使用std::reverse_iterator实现逆向遍历vector，也可以使用std::reverse函数。

/*
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> > rtVec;
        if(!pRoot) return rtVec;
        vector<TreeNode*> nodes;
        nodes.push_back(pRoot);
        PrintCore(rtVec, nodes, true);
        return rtVec;
    }
    // rtVec, in/out, save the output result
    // nodes, in, nodes of current layers
    // l2r, in, if the output/loop order is from left to right
    void PrintCore(vector<vector<int> > &rtVec, vector<TreeNode*> nodes, bool l2r){
        if(0 == nodes.size()) return;
        vector<TreeNode*> subNodes;
        vector<int> vCurLayer;
        vector<TreeNode*>::reverse_iterator it;
        for(it = nodes.rbegin(); it != nodes.rend(); it++){
            vCurLayer.push_back((*it)->val);
            if(l2r){
                if((*it)->left) subNodes.push_back((*it)->left);
                if((*it)->right) subNodes.push_back((*it)->right);
            }else{
                if((*it)->right) subNodes.push_back((*it)->right);
                if((*it)->left) subNodes.push_back((*it)->left);
            }
        }
        rtVec.push_back(vCurLayer);
        PrintCore(rtVec, subNodes, !l2r);
    }
};