【剑指Offer】序列化二叉树

﹏ヽ暗。殇╰゛Y 2022-03-14 14:26 189阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=11214&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_cf7e25aa97c04cc1a68c8f040e71fb84_tpId_13_tqId_11214_tPage_4_rp_4_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

请实现两个函数，分别用来序列化和反序列化二叉树

#### 解决方法 ####

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */
    class Solution { 
    public:
        char* Serialize(TreeNode *root) {     
            if(!root) return "#";
            string r = to_string(root->val);
            r.push_back(',');
            char *left = Serialize(root->left);
            char *right = Serialize(root->right);
            char *ret = new char[strlen(left) + strlen(right) + r.size()];
            strcpy(ret, r.c_str());
            strcat(ret, left);
            strcat(ret, right);
            return ret;
        }
        
        TreeNode* Deserialize(char *str) { 
            return decode(str);
        }
        TreeNode* decode(char *&str) { 
            if(*str=='#'){ 
                str++;
                return NULL;
            }
            int num = 0;
            while(*str != ',')
                num = num*10 + (*(str++)-'0');
            str++;
            TreeNode *root = new TreeNode(num);
            root->left = decode(str);
            root->right = decode(str);
            return root;
        }
    };

[https_www.nowcoder.com_practice_cf7e25aa97c04cc1a68c8f040e71fb84_tpId_13_tqId_11214_tPage_4_rp_4_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=11214&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking