1 思路

累计耗时超过1小时！！

  • 請站在模板的肩上
  • 自己尝试利用双端队列的代码，其实可以用普通队列
  • 【要点】主要是内部vector插入的时候，选择尾部更新，还是头部更新的问题，这样就不用排序了，
  • 难点不是queque pop, 而是在内部数据插入的维护上；

难点的地方 2处

如图圈主的地方 alt

vector操作

alt

层次遍历 /BFS模板的认识

alt

更多的参考https://blog.nowcoder.net/n/b169fcd8c60b446eae5869a319a3c7ef

2 code

//自己尝试利用双端队列的代码，其实可以用普通队列
//主要是内部vector插入的时候，选择尾部更新，还是头部更新的问题，这样就不用排序了

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <deque>
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        int level = 1;

        vector<vector<int> > finalV;
        if(!pRoot){
            return finalV;
        }
        deque<TreeNode*> dq;//dq(pRoot);
        dq.push_back(pRoot);
        
        int curr = 0;
        TreeNode* currNode = NULL;
        while( !dq.empty()){
            int sz = dq.size();//每一层数目
            vector<int> innerV;
            
            while( sz--){
                
                //if( level%2 ==1){
                    currNode = dq.front();
                    curr = dq.front()->val;
                    dq.pop_front();
                    
                //}else{
//                     currNode = dq.back();
//                     curr = dq.back()->val;
//                     dq.pop_back();
//                 }
                if( level%2 ==1){
                  innerV.push_back(curr);
                }else{
                  innerV.insert(innerV.begin(),curr);//similar to push front
                }

                if(currNode->left)
                    dq.push_back(currNode->left);
                if(currNode->right)
                    dq.push_back(currNode->right);
            }
            level++;
            finalV.push_back(innerV);
        }
        
        return finalV;
    }
    
};