题解 | #c++ 简单却复杂的广度遍历 #

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    
    /* ***************后序、中序、先序建树不太好懂，直接采用广度序列************/
    /*  先说思路，以前的曾序遍历，在左右子节点不为空的时候插入，现在是
     *  如果为空插入一个假的结点。
     *  那么在构造树的时候当碰见这些假的结点返回空就行了。
     
     *  *********************变量区*************************
     *  n  用来存放总节点个数                   
     *  results 用来存放遍历结果
     
     *  *********************注意点*************************
     *  一定需要注意的是，不同类型强转特别容易出错，题目给的是小于100的value,后来却有个150
     *  所以在将int强转成char的时候，一定要转化为 无符号的char 否则过不了
     */
    int n;
    char* results;
  
  
  
    /*  ********************调用区**************************/
    char* Serialize(TreeNode *root) {
        this->n = pow(2,(dfsserch(root)))-1;//根据深度求出总结点个数 --》81行
        this->results = new char[n]; //生成对应长度数组
        return bfsserch(root); //开始曾序遍历，--》40行
    }
    TreeNode* Deserialize(char *str) {
        return creatTree(str, 1);//根据char* 建树--》 64行
    }
    
  
    /* ********************外部函数区*********************/
    /*曾序遍历序列*/
    char* bfsserch(TreeNode* root){
        if(root == nullptr){
            return nullptr;
        }else{
            queue<TreeNode*> nodes;nodes.push(root);
            int index = 0;//index是数组下标索引
            while(!nodes.empty() && index < n){
                int size = nodes.size();
                while(size>0){
                    auto temp = nodes.front();
                    nodes.pop();size--;results[index] = (unsigned char)temp->val;
                    if(temp->left){nodes.push(temp->left);}else{
                        TreeNode* fool = new TreeNode(-1);
                        nodes.push(fool);
                    }
                    if(temp->right){nodes.push(temp->right);}else{
                        TreeNode* fool = new TreeNode(-1);
                        nodes.push(fool);
                    }index++;
                }
            }
            return results;
        }
    }
    /*递归建树子函数*/
    TreeNode* creatTree(char* str,int cur){
        if(cur > n){
            return nullptr;
        }else{
            if((int)str[cur-1] == -1){
                //碰见假的结点返回空
                return nullptr;
            }
            TreeNode* head = new TreeNode((unsigned char)str[cur-1]);
           // int left = cur*2-1;int right = cur*2;
            head->left = creatTree(str,cur*2);
            head->right = creatTree(str, cur*2+1);
            return head;
        }
    }
    /*返回深度，防止空间浪费*/
    int dfsserch(TreeNode* node){
        if(node == nullptr){
            return 0;
        }else{
             int left = dfsserch(node->left);
             int right = dfsserch(node->right);
             return max(left,right)+1;
        }
    }
};