Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.
Approach 1.
========
Convert the given BST into a doubly linked list in O(n) and then send the linked list over the channel.
Note:: See Blog Convert tree into linked list in O(n) using tree rotations.
Once you recieve the tree then again convert back the linked list to tree. I haven't done this yet in O(n); however there is a post avaiabe; if you have a solution for second case please do post.
Approach 2
========
1. Take the preorder traversal of the tree; write it to a file and send it over the channel. This would be done using O(n).
Since you have to traverse the tree to save the nodes.
Possible traversals are inorder, preorder, postorder and level order.
If we do an inorder traversal then we would get a sorted list which if we convert into a BST would again become a list and we would loose out on the original structure of the tree.
Postorder traversal would also not give back the original tree; a simple example can let you know.
Now left out are preorder and level order traversal.
Both give us the output; but level order will require more space as it uses BFS approach. So we do a preorder traversal of the tree store it in a file in O(n) and send it over the channel.
On the recieving end we recieve and construct the tree back in O(n log(n)); by inserting each and every node in the preorder list into the new list using the property of BST results the same tree....
class TreeNode{ int val; TreeNode left, right; TreeNode(int val){ this.val = val; } } public String serialize(TreeNode root){ StringBuilder sb = new StringBuilder(); serialize(root, sb); return sb.toString(); } private void serialize(TreeNode x, StringBuilder sb){ if (x == null) { sb.append("# "); } else { sb.append(x.val + " "); serialzie(x.left, sb); serialzie(x.right, sb); } } public TreeNode deserialize(String s){ if (s == null || s.length() == 0) return null; StringTokenizer st = new StringTokenizer(s, " "); return deserialize(st); } private TreeNode deserialize(StringTokenizer st){ if (!st.hasMoreTokens()) return null; String val = st.nextToken(); if (val.equals("#")) return null; TreeNode root = new TreeNode(Integer.parseInt(val)); root.left = deserialize(st); root.right = deserialize(st); return root; }
References:
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/
http://www.cs.usfca.edu/~galles/cs245/lecture/lecture9.pdf
相关推荐
leetcode-tag-Tree
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode 答案解析 golang解答
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
示例1输入: 1 1**示例2**输入: 1 1代码实现Definition for a binary tree node.本文链接: https://www.
leetcode 答案leetcode 的工具 这个项目提供了一些工具来更容易地测试 ...github.com/zhai3516/leetcode-tools/lckit 用法 lckit --kit=tmp --name="Flatten Binary Tree to Linked List" --type=tree
leetcode-tag-Stack