LeetCode 297 Serialize and Deserialize Binary Tree

    
        标签：
        
            二叉树
        
            LeetCode
        
    发布于：2022-02-07 23:02:12
    编辑于：2022-02-07 23:14:40
    浏览量：758

概述

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

递归法

一般语境下，单单前序遍历结果是不能还原二叉树结构的，因为缺少空指针的信息，至少要得到前、中、后序遍历中的两种才能还原二叉树。但是这里的 node 列表包含空指针的信息，所以只使用 node 列表就可以还原二叉树。

为什么包含空指针后就可以确保能还原？不妨这样理解，对于叶节点，我们肯定能正确还原该节点，因此对于其父节点我们肯定也能正确还原，由此自下向上我们就都可以还原了。

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "#,";
        string s = to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
        return s;
    }
    
    queue<TreeNode*> nodes;
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string s;
        for (auto c : data) {
            if (c == ',') {
                if (s == "#") {
                    nodes.push(nullptr);
                } else {
                    nodes.push(new TreeNode(stoi(s)));
                }
                s = "";
            } else {
                s += c;
            }
        }
        return helper();
    }
    
    TreeNode* helper() {
        auto root = nodes.front();
        nodes.pop();
        if (!root) return nullptr;
        root->left = helper();
        root->right = helper();
        return root;
    }
};

使用其他遍历顺序的解法：https://mp.weixin.qq.com/s/DVX2A1ha4xSecEXLxW_UsA

其中后续遍历的方法与前序遍历的很接近，无非是换了下顺序。

迭代法

基于层次遍历的方法的序列换和反序列化都是迭代实现的。

反序列化时，其也是一层一层得吃掉 node 列表并一层一层构建 tree 的。

Links: leetcode-297-serialize-and-deserialize-binary-tree