一.概念理解:
题目如下:https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/
何为序列化?
序列化我们可以理解为层序遍历的结果,即将所有的结点的信息,按照层序遍历的结果拼接到一个字符串中,但是与一般的层序遍历有所不同的是:序列化要输出所有的结点信息,而层序遍历一般不会对null结点进行输出。如下:
二.解决思路:
1.序列化:
既然与层序遍历存在相同之处,那么解决思路同样存在相同之处了:
我们解决层序遍历的题目时,一般利用辅助队列空间,即创建一个存放结点的LinkedList,判断当前结点是否非空,不为空则加入到队列中,同时设置一个计数器:不断记录当前队列中存在几个元素,后面输出,力扣题目以及代码如下:
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[0];
Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
ArrayList<Integer> ans = new ArrayList<>();
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
ans.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++)
res[i] = ans.get(i);
return res;
}
}
作者:jyd
链接:https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
序列化不需要设置计数器,但是遍历的思路和其完全相同,但是序列化需要利用StringBuilder进行字符串的拼接,就是将每次放入队列的元素拼接到StringBuilder中,null也需要拼接,通过判断队列是否为空,进行不断的循环:
public String serialize(TreeNode root) {
//检验头结点的合法性
if(root == null) return "[]";
//拼接左括号
StringBuilder res = new StringBuilder("[");
//将头结点接入
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
//由于null也需要加入队列,所以这时需判断加入队列的元素是否为null
if(node != null) {
// 将当前结点进行拼接
res.append(node.val + ",");
//
queue.add(node.left);
queue.add(node.right);
}
//如果是null直接在StringBuilder中拼接null
else res.append("null,");
}
//将最后一个逗号删除
res.deleteCharAt(res.length() - 1);
//拼接右半部分括号
res.append("]");
return res.toString();
2.反序列化
反序列化可以理解为序列化的逆过程:在序列化字符串中按照下标不断取出新的元素,并判断是否为空,不是空则加入到辅助队列中,不断循环直至队列中的元素为空:循环结束。文章来源:https://www.toymoban.com/news/detail-540932.html
具体实现逻辑的代码如下:文章来源地址https://www.toymoban.com/news/detail-540932.html
public TreeNode deserialize(String data) {
//如果序列化字符串中的元素为空,直接返回null
if(data.equals("[]")) return null;
//转化为字符串数组,便于节点的遍历
String[] vals = data.substring(1, data.length() - 1).split(",");
//先将第一个元素加入队列
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
int i = 1;
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
//以队列是否为空为不断循环的条件
if(!vals[i].equals("null")) {
//当前不为空则加入到队列,并将其作为当前元素的左子节点
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.left);
}
i++;
if(!vals[i].equals("null")) {
//当前不为空则加入到队列,并将其作为当前元素的右子节点
node.right = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.right);
}
i++;
}
//反序列化结束,返回根节点
return root;
}
到了这里,关于刷题日记01:序列化和反序列化二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!