(js)leetcode 297. 二叉树的序列化与反序列化

ゝ一世哀愁。 2022-11-07 04:07 244阅读 0赞

题目:

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

示例 1:

9387977615b7e602406be82d7d4452b9.png
输入:root = [1,2,3,null,null,4,5]
输出:[1,2,3,null,null,4,5]
示例 2:

输入:root = []
输出:[]
示例 3:

输入:root = [1]
输出:[1]
示例 4:

输入:root = [1,2]

思路:

使用前序遍历

可参考官方解答

代码实现:

  1. /**
  2. * Definition for a binary tree node.
  3. * function TreeNode(val) {
  4. * this.val = val;
  5. * this.left = this.right = null;
  6. * }
  7. */
  8. /**
  9. * Encodes a tree to a single string.
  10. *
  11. * @param {TreeNode} root
  12. * @return {string}
  13. */
  14. var serialize = function (root) {
  15. let res = rserialize(root, '');
  16. return res;
  17. };
  18. var rserialize = function (root, str) {
  19. if (root == null) {
  20. str += '#,';
  21. } else {
  22. str += root.val + ',';
  23. str = rserialize(root.left, str);
  24. str = rserialize(root.right, str);
  25. }
  26. return str;
  27. }
  28. /**
  29. * Decodes your encoded data to tree.
  30. *
  31. * @param {string} data
  32. * @return {TreeNode}
  33. */
  34. var deserialize = function (data) {
  35. let arr = data && data.split(',') || [];
  36. return rdeserialize(arr);
  37. };
  38. var rdeserialize = function (data) {
  39. if(data.length == 0) return null;
  40. let first = data.shift();
  41. if(first == '#') return null;
  42. let root = new TreeNode(parseInt(first));
  43. root.left = rdeserialize(data);
  44. root.right = rdeserialize(data);
  45. return root;
  46. };
  47. /**
  48. * Your functions will be called as such:
  49. * deserialize(serialize(root));
  50. */

运行结果:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70

发表评论

表情:
评论列表 (有 0 条评论,244人围观)

还没有评论,来说两句吧...

相关阅读

    相关 序列/序列

    二叉树被记录成文件的过程,为二叉树的序列化 通过文件重新建立原来的二叉树的过程,为二叉树的反序列化 设计方案并实现。 (已知结点类型为32位整型) 思路:先序遍历实现。