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

//反向遍历每层时保存下一层

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>> retVec;
        if (!pRoot) return retVec;
        
        vector<TreeNode *> nextLevelNodes, curLevelNodes;
        vector<int> curLevelVec;
        bool ltor = true;
        
        curLevelNodes.push_back(pRoot);
        
        while (curLevelNodes.size()) {
            curLevelVec.clear();
            for (vector<TreeNode*>::reverse_iterator it = curLevelNodes.rbegin(); it!=curLevelNodes.rend(); ++it) {    //反向遍历当前层，按方向保存下一层
                if (ltor && (*it)->left) nextLevelNodes.push_back((*it)->left);    //左右方向则先保存左
                if ((*it)->right) nextLevelNodes.push_back((*it)->right);
                if (!ltor && (*it)->left) nextLevelNodes.push_back((*it)->left);    //右左方向则先保存右
                curLevelVec.push_back((*it)->val);    //依次当前层所有值
            }
            if (!curLevelVec.empty()) retVec.push_back(curLevelVec);    //当前层值非空则保存
            ltor = !ltor;    //方向调整
            curLevelNodes = nextLevelNodes;  //下一层赋予当前层
            nextLevelNodes.clear();    //清除下层容器
        }
        
        return retVec; 
        
/*        vector<vector<int>> retVec;
        if (!pRoot) return retVec;
        
        bool ltor = true;
        queue<TreeNode*> nodes;
        
        nodes.push(pRoot);
        
        while (nodes.size()) {
            int size = nodes.size();
            vector<int> vec;
            
            while (size--) {
                TreeNode *node = nodes.front();
                
                nodes.pop();
                vec.push_back(node->val);
                
                if (ltor && node->left) nodes.push(node->left);
                if (node->right) nodes.push(node->right);
                if (!ltor && node->left) nodes.push(node->left);
            }
            
            if (vec.size()) retVec.push_back(vec);    //保存该层值
            
            ltor = !ltor;    //调整方向
            if (nodes.size()) { //调整方向
                vector<TreeNode *> tmpNodes;
                while (nodes.size()) {
                    tmpNodes.push_back(nodes.front()); 
                    nodes.pop();
                }
                for (auto it=tmpNodes.rbegin(); it!=tmpNodes.rend(); ++it)
                    nodes.push(*it);
            }
        }
        
        return retVec; */
    }
    
};