题解 | #序列化二叉树#

序列化二叉树

http://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84

1. 先序遍历解法

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    const char SEP = '&';
    const char NULL_NODE = '#';
    char* Serialize(TreeNode *root) {    
        if(!root){
            return nullptr;
        }
        stack<TreeNode*> nodes;
        TreeNode* cur = root;
        string s;
        
        while(cur || !nodes.empty()){
            while(cur){
                s.append(to_string(cur->val));
                s.push_back(SEP);
                nodes.push(cur);
                cur = cur->left;
            }
            s.push_back(NULL_NODE);
            s.push_back(SEP);
            cur = nodes.top();
            nodes.pop();
            cur = cur->right;
        }
        s.push_back(NULL_NODE);
        s.push_back(SEP);
        char* ret = new char[s.length() + 1];
        strcpy(ret, s.c_str());
        return ret;
        
    }
    
    TreeNode* Deserialize(char *str) {
        if(!str){
            return nullptr;
        }
        string s(str);
        TreeNode* root = new TreeNode(atoi(s.c_str()));
        s = s.substr(s.find_first_of(SEP) + 1);
        TreeNode* cur = root;
        stack<TreeNode*> nodes;
        while(!s.empty() && (cur || !nodes.empty())){
            while(cur){
                nodes.push(cur);
                if(s[0] == NULL_NODE){
                    cur->left = nullptr;
                }else{
                    cur->left = new TreeNode(atoi(s.c_str()));
                }
                s = s.substr(s.find_first_of(SEP)+1);
                cur = cur->left;
            }
            cur = nodes.top();
            nodes.pop();
            if(s[0] == NULL_NODE){
                cur->right = nullptr;
            }else{
                cur->right = new TreeNode(atoi(s.c_str()));
            }
            s = s.substr(s.find_first_of(SEP)+1);
            cur = cur->right;
        }
        return root;
    }
};

2. 层序遍历解法

class Solution {
public:
    const char SEP = '&';
    const char NULL_NODE = '#';
    char* Serialize(TreeNode *root) {
        if(!root){
            return nullptr;
        }
        queue<TreeNode*> nodes;
        nodes.push(root);
        string serialized_str;
        while(!nodes.empty()){
            TreeNode* head = nodes.front();
            nodes.pop();
            if(head){
                serialized_str.append(to_string(head->val));
                nodes.push(head->left);
                nodes.push(head->right);
            }else{
                serialized_str.push_back(NULL_NODE);
            }
            serialized_str.push_back(SEP);
        }
        char* ret = new char[serialized_str.length() + 1];
        strcpy(ret, serialized_str.c_str());
        return ret;
    }
    TreeNode* Deserialize(char *str) {
        if(!str){
            return nullptr;
        }
        string s(str);
        if(s[0] == NULL_NODE){
            return nullptr;
        }
        queue<TreeNode*> nodes;
        TreeNode* root = new TreeNode(atoi(s.c_str()));
        nodes.push(root);
        s = s.substr(s.find_first_of(SEP)+1);
        
        while(!nodes.empty() && !s.empty()){
            TreeNode* head = nodes.front();
            nodes.pop();
            if(s[0] == NULL_NODE){
                head->left == nullptr;
            }else{
                head->left = new TreeNode(atoi(s.c_str()));
                nodes.push(head->left);
            }
            s = s.substr(s.find_first_of(SEP) + 1);
            
            if(s[0] == NULL_NODE){
                head->right = nullptr;
            }else{
                head->right = new TreeNode(atoi(s.c_str()));
                nodes.push(head->right);
            }
            s = s.substr(s.find_first_of(SEP) + 1);
        }
        return root;
    }
};