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

数据结构 双端队列 C++
一端受限的队列无法解决反向输出问题，那就双端嘛。思路同层次遍历一样，用r来记录当前层最后一个入队节点，时间复杂度为O(n)，n为树的节点数；空间复杂度为O(n)。

vector<vector<int> > Print(TreeNode* pRoot) {
        TreeNode* r = pRoot; //层次遍历，记录当前层最后一个入队节点
        deque<TreeNode*> q;//双端队列
        vector<vector<int>> ans;
        if(pRoot==NULL)
            return ans;
        q.push_front(pRoot);
        vector<int> floor; //每层节点值的集合
        for(int i=0;!q.empty();){
            TreeNode* tmp;
            if(i%2==0){
                tmp=q.front();
                floor.push_back(tmp->val);
                if(tmp->left!=NULL)
                    q.push_back(tmp->left);
                if(tmp->right!=NULL)
                    q.push_back(tmp->right);
                q.pop_front();
                if(r==tmp){ //扫描到本层最后一个
                    ans.push_back(floor);
                    floor.clear();
                    r=q.front();
                    i++;
                }
            }
            else{
                tmp=q.back(); 
                floor.push_back(tmp->val);
                if(tmp->right!=NULL)
                    q.push_front(tmp->right);
                if(tmp->left!=NULL)
                    q.push_front(tmp->left);
                q.pop_back();
                if(r==tmp){
                    ans.push_back(floor);
                    floor.clear();
                    r=q.back();
                    i++;
                }
            }

        }
        return ans;
    }