LeetCode 297. 二叉树的序列化与反序列化

题目链接：

力扣https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

【分析】序列化的时候很简单，任意的一种二叉树遍历都可以做到，关键是怎么保存树的结构特征，我们可以通过先序遍历的过程中保存null节点来实现。

以样例一为🌰：保存null节点的先序遍历结果为：1,2,null,null,3,4,null,null,5,null,null

在反序列化的过程中，仍然按照先序，

1.取出头节点1，创建为root，剩下的[2,null,null,3,4,null,null,5,null,null]，递归调用构造函数去创建root的left和right。

2.在创建left的过程中，取出头节点2，作为root，剩下的[null,null,3,4,null,null,5,null,null]部分继续调用构造函数，由于头节点为null，直接返回作为root的left，那么root的right部分的构造函数传入的链表就是[null,3,4,null,null,5,null,null]了，头节点同样为null，直接返回作为root的right，这样节点2至此就完全创建好了，值为2，左右节点为null，他返回作为1节点的left。

3.接下来到了创建1节点的right了，剩余的链表中的内容还有[3,4,null,null,5,null,null]，取出头节点3作为right的root节点，然后递归将[4,null,null,5,null,null]继续创建。

总结下来其实这个主要通过对null值的直接返回来保存结构，此外在构建的过程中链表中的节点不断减少。

public class Codec {List list = new ArrayList();public void dfs(TreeNode node){if(node == null) list.add(1001);else{list.add(node.val);dfs(node.left);dfs(node.right);}}// Encodes a tree to a single string.public String serialize(TreeNode root) {dfs(root);return list.toString();}public TreeNode dsrz(Deque queue){int top = queue.poll();if(top == 1001) return null;TreeNode root = new TreeNode(top);root.left = dsrz(queue);root.right = dsrz(queue);return root;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] strs = data.substring(1, data.length() - 1).split(",");Deque queue = new LinkedList();for(var str: strs) queue.offer(Integer.parseInt(str.trim()));return dsrz(queue);}
}

这里有一个小小的作弊的方法，可以不转字符串。改一下函数的返回值

public class Codec {Deque list = new LinkedList();public void dfs(TreeNode node){if(node == null) list.offer(1001);else{list.offer(node.val);dfs(node.left);dfs(node.right);}}// Encodes a tree to a single string.public Deque serialize(TreeNode root) {dfs(root);return list;}public TreeNode dsrz(Deque queue){int top = queue.poll();if(top == 1001) return null;TreeNode root = new TreeNode(top);root.left = dsrz(queue);root.right = dsrz(queue);return root;}// Decodes your encoded data to tree.public TreeNode deserialize(Deque queue) {return dsrz(queue);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！