LeetCode 297 Serialize and Deserialize Binary Tree

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

概述

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 的。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/