1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 37 题] “序列化二叉树”做题记录

[剑指 Offer 第 2 版第 37 题] “序列化二叉树”做题记录

第 37 题:序列化二叉树

传送门:序列化二叉树牛客网 online judge 地址

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

您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。

样例:

你可以序列化如下的二叉树 8 / \ 12 2 / \ 6 4 为:"[8, 12, 2, null, null, 6, 4, null, null, null, null]"

注意:

  • 以上的格式是 AcWing 序列化二叉树的方式,你不必一定按照此格式,所以可以设计出一些新的构造方式。

分析:总之就是前序遍历。因为“前序遍历”有很好的性质:

liwei2019101113_1.png

说明:根据上面的序列化规则,上图中的二叉树被序列化成字符串 "1,2,4,,3,5,,6,,$"

Python 代码:

  class Solution:

        # 前序遍历
        def serialize(self, root):
            """Encodes a tree to a single string.

            :type root: TreeNode
            :rtype: str
            """

            res = ''
            if root is None:
                return '! '
            res += str(root.val)
            res += ' '
            res += self.serialize(root.left)
            res += self.serialize(root.right)
            return res

        def deserialize(self, data):
            """Decodes your encoded data to tree.

            :type data: str
            :rtype: TreeNode
            """
            arr = data.split(' ')
            return self.__helper(arr)

        def __helper(self, arr):
            if arr:
                top = arr.pop(0)
                if top != '!':
                    root = TreeNode(int(top))
                    root.left = self.__helper(arr)
                    root.right = self.__helper(arr)
                    return root
                else:
                    return None

Python 代码:序列化时候,不用递归,用栈的写法

  class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None


    class Solution:

        # 前序遍历
        def serialize(self, root):
            """Encodes a tree to a single string.

            :type root: TreeNode
            :rtype: str
            """

            res = []
            if root is None:
                return '!'

            stack = [root]
            while stack:
                top = stack.pop()
                if top is None:
                    res.append('!')
                else:
                    stack.append(top.right)
                    stack.append(top.left)
                    res.append(str(top.val))
            return ' '.join(res)

        def deserialize(self, data):
            """Decodes your encoded data to tree.

            :type data: str
            :rtype: TreeNode
            """
            queue = data.split(' ')
            return self.__build_tree(queue)

        def __build_tree(self, queue):
            if queue:
                top = queue.pop(0)
                if top != '!':
                    root = TreeNode(int(top))
                    root.left = self.__build_tree(queue)
                    root.right = self.__build_tree(queue)
                    return root
                else:
                    return None
            # 如果 queue 为空,就什么都不做

Java 代码:序列化:前序遍历二叉树存入字符串中,反序列化:根据前序遍历重建二叉树

  import java.util.LinkedList;

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Solution {

        /**
         * 序列化一棵二叉树(其实就是前序遍历)
         * @param root
         * @return
         */
        public String serialize(TreeNode root) {
            if (root == null) {
                return "$,";
            }
            StringBuilder sb = new StringBuilder(root.val + ",");
            sb.append(serialize(root.left));
            sb.append(serialize(root.right));
            return sb.toString();
        }

        // 反序列化一棵二叉树
        public TreeNode deserialize(String str) {
            String[] strArr = str.split(",");
            LinkedList<String> queue = new LinkedList<>();
            for (String s : strArr) {
                queue.addLast(s);
            }
            return preOrder(queue);
        }

        // 使用队列就实现了迭代器的功能
        private TreeNode preOrder(LinkedList<String> queue) {
            String s = queue.removeFirst();
            if (!"$".endsWith(s)) {
                TreeNode newNode = new TreeNode(Integer.parseInt(s));
                newNode.left = preOrder(queue);
                newNode.right = preOrder(queue);
                // 理解将新创建的结点返回回去的必要性
                return newNode;
            }
            // 是 "$" 就返回空指针,注意这里的递归方法,会把空指针接在原来的树节点上
            return null;
        }
    }

另一种写法:

Java 代码:

  import java.util.LinkedList;

    // 前序遍历
    public class Solution2 {

        String Serialize(TreeNode root) {
            StringBuilder stringBuilder = new StringBuilder();
            preOrder(root, stringBuilder);
            return stringBuilder.toString();
        }

        // 上面函数的辅助函数
        private void preOrder(TreeNode node, StringBuilder stringBuilder) {
            if (node == null) {
                stringBuilder.append("#");
                stringBuilder.append(",");
                return;
            }
            stringBuilder.append(node.val);
            stringBuilder.append(",");
            preOrder(node.left, stringBuilder);
            preOrder(node.right, stringBuilder);
        }

        TreeNode Deserialize(String str) {
            String[] strings = str.split(",");
            int size = strings.length;
            System.out.println(size);
            LinkedList<String> queue = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                queue.addLast(strings[i]);
            }
            return inOrderGenerate(queue);
        }

        private TreeNode inOrderGenerate(LinkedList<String> queue) {
            if (queue.isEmpty()) {
                return null;
            }
            String s = queue.removeFirst();
            if (!"#".equals(s)) {
                TreeNode root = new TreeNode(Integer.parseInt(s));
                root.left = inOrderGenerate(queue);
                root.right = inOrderGenerate(queue);
                return root;
            }
            return null;
        }
    }

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:

        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string res;
            dfs_s(root, res);
            return res;
        }

        void dfs_s(TreeNode *root, string &res)
        {
            if (!root) {
                res += "null ";
                return;
            }
            res += to_string(root->val) + ' ';
            dfs_s(root->left, res);
            dfs_s(root->right, res);
        }

        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int u = 0;
            return dfs_d(data, u);
        }

        TreeNode* dfs_d(string &data, int &u)
        {
            if (u == data.size()) return NULL;
            int k = u;
            while (data[k] != ' ') k ++ ;
            if (data[u] == 'n') {
                u = k + 1;
                return NULL;
            }
            int val = 0;
            for (int i = u; i < k; i ++ ) val = val * 10 + data[i] - '0';
            u = k + 1;
            auto root = new TreeNode(val);

            root->left = dfs_d(data, u);
            root->right = dfs_d(data, u);

            return root;
        }
    };

作者:yxc 链接:https://www.acwing.com/activity/content/code/content/20710/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「方志朋」,公众号后台回复「666」 免费领取我精心整理的进阶资源教程
  4. JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

    本文著作权归作者所有,如若转载,请注明出处

    转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

    标题:[剑指 Offer 第 2 版第 37 题] “序列化二叉树”做题记录

    链接:https://www.javajike.com/article/3284.html

« [剑指 Offer 第 2 版第 36 题] “二叉搜索树与双向链表”做题记录
[剑指 Offer 第 2 版第 38 题] “字符串的排列”做题记录»

相关推荐

QR code