面试热点|二叉树那点事儿(一)中

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //处理每个层的数据:将null清除 将string转换为int 根据层数进行翻转
    bool revseit(vector<string> &vec, int curlevl, vector<int> &res){
        //由于层数是从1开始编号 因此满足奇数层从左到右不翻转 偶数层翻转为从右向左
        vector<string>::iterator iter = vec.begin();
        for(;iter!=vec.end();iter++){
            if(*iter=="null")
                continue;
            res.push_back(std::stoi(*iter));
        }
        if(curlevl%2==0)
            std::reverse(res.begin(),res.end());
        return true;
    }
    //开始处理由二叉树构造满二叉树生成的vector
    bool dealit(vector<string> &vec, vector<vector<int> > &res){ 
        //从顶向下按照满二叉树切割每层 每层结点数遵循 等比数列 1 2 4 8 .... 2^(k-1) k=1,2,3...
        //满二叉树的总结点数量S=2^k-1 由此可以计算层数 也就是子vector的数量
        int nodecnt = vec.size();
        int levcnt = log(nodecnt+1)/log(2);
        //这一步是判断完全二叉树的情况
        bool notfull = false;
        if(pow(2,levcnt)-1!=nodecnt){
            notfull=true;
        }
        //我们从第1层开始向后分层切割
        int curlevl = 1;
        vector<string> tmpvec;
        vector<int> tmpsubres;
        while(curlevl<=levcnt+1){
            //临时结构清空
            tmpvec.clear();
            tmpsubres.clear();
            //计算本层之前的全部结点数量 作为本次切片的起点
            int lastsum = pow(2,curlevl-1)-1;
            //计算本层的节点数 作为切片时的偏移量
            int gap = pow(2,curlevl-1);
            if(curlevl==levcnt+1){
                if(notfull)
                    gap = nodecnt-lastsum;
                else
                    break;
            }     
            tmpvec.assign(vec.begin()+lastsum,vec.begin()+lastsum+gap);
            revseit(tmpvec,curlevl,tmpsubres);
            if(tmpsubres.size()>0)
                res.push_back(tmpsubres);
            curlevl++;
        }
        return true;
    }
    //非递归层次遍历 注意空节点的处理
    void travese(TreeNode *root, vector<string> &vec){
        //相当于一个标记位 记录队列中非空节点数量
        int oknodecnt = 0; 
        TreeNode *node = root;
        queue<TreeNode*> q;
        q.push(node);
        oknodecnt++;
        while(!q.empty()&&oknodecnt>0)
        {
            TreeNode *top = q.front();
            if(top){
                //向队列装载左结点
                if(top->left){
                    q.push(top->left);
                    oknodecnt++;
                }else
                    q.push(NULL);
                //向队列装载右节点
                if(top->right){
                    q.push(top->right);
                    oknodecnt++;
                }else
                    q.push(NULL);
                //队头节点任务完成 可以弹出并加入到vector中
                q.pop();
                oknodecnt--;
                vec.push_back(std::to_string(top->val));
            }else{
                //当队头节点时NULL时 为了保证满二叉树的特性 向队列中增加两个NULL作为其虚拟孩子节点
                q.pop();
                q.push(NULL);
                q.push(NULL);
                vec.push_back("null");
            }
        }
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int> > res;
        vector<string> vectree;
        if(!root)
            return res;
        //层次遍历
        travese(root,vectree);
        //处理遍历后生成的vector
        dealit(vectree,res);
        return res;
    }
};