算法1

(层级遍历) $O(n)$

C++ 代码

/**
 * 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:
    string int2str(int k){
       string s="";
       int val = k;
        if (k<0) val *= (-1);
       while(val>0){
           s.push_back((val % 10)+'0');
           val /= 10;
       }
       if (k < 0) s.push_back('-');
       reverse(s.begin(),s.end());
       return s;
    }
    string res = "";
    void dfs(TreeNode* root){
        if(root==NULL){
            res.push_back('#');
            res.push_back(' ');
            return ;
        }
        res+=int2str(root->val);
        res.push_back(' ');
        dfs(root->left);
        dfs(root->right);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s = "";
        if (root==NULL) return s;
        // dfs(root);
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* c = q.front();
            q.pop();
            if (c!=NULL){
            q.push(c->left);
            q.push(c->right);
            }



            if (c!=NULL) {
                s = s + int2str(c->val);

                    s+=" ";

            }
            else if(c==NULL){
                s = s+"#";

                    s+=" ";

            }

        }

        return s;

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.size()==0) return NULL;
        // cout<<data<<endl;
        int last = 0;
        vector<TreeNode*> v;
        int sum = 0;
        for(int i=0;i<data.size();i++){
            string s;
            if(data[i] == ' '){
                s = data.substr(last,i);

                last = i;

                if(s[0]=='#'){
                    v.push_back(NULL);
                }
                else{
                    TreeNode* c = new TreeNode(sum);
                    v.push_back(c);
                }
                 sum = 0;
            }
            else if (data[i]>='0' && data[i]<='9'){
                sum = sum * 10 + data[i]-'0';
            }

            }
        queue<TreeNode*> q;
        int k = 0;
        auto  root = v[0];
        q.push(root);
        while(k<v.size()&&!q.empty()){
            auto cur = q.front();
            //  cout<<cur->val<<endl;
            q.pop();

            if(k+1>v.size()) break;

            if (v[k+1]->val == 0){
                 cur->left =  NULL;
            }
            else{
                cur->left = v[k+1];
                q.push(v[k+1]);

            }

            if (v[k+2]->val == 0){
                 cur->right = NULL;
            }
            else{
                 cur->right = v[k+2];
                 q.push(v[k+2]);
            }
            k+=2;    

        }


        return v[0];
    }
};