思路
题目分析
- 题目给出我们一棵树，要求我们实现两个函数
- 第一个函数要求我们以任意遍历方式返回一个字符串
- 第二个函数要求我们可以从上一个字符串中重新返回这棵树
-
方法一：递归
- 我们采用前序遍历的方式构造字符串并恢复树
- 序列化过程
- 递归函数退出条件是当节点为空，则返回
"#"。我们一定要用一个"#"来实现占位的操作，这样才能保证我们的树是唯一的，否则单独前序遍历出来的字符串是无法恢复成唯一的一棵树的 - 然后我们递归地返回
当前值+","+递归左子节点+","+递归右子节点
- 递归函数退出条件是当节点为空，则返回
- 反序列化过程
- 我们引入了一个新的结构queue来储存字符串分割后的前序遍历结果
- 由于前序遍历，我们首先从queue中取出队首，将其对象化成为一个节点
- 然后将左子节点值设为递归这个queue的函数返回结果
- 然后将右子节点值设为递归这个queue的函数返回结果
- 这正好符合了前序遍历的规则，我们倒着又建立了这棵树
-
方法二：迭代
- 我们采用层序遍历的方式迭代
- 序列化过程
- 队列中存储一层的节点信息
- 遍历该层的时候进行对字符串的构造
- 同时不断地压入下一层的节点信息
- 最终给返回字符串
- 反序列化过程
- 引入一个aux队列来辅助建立树
- aux队列首先同样拿到一层的节点信息
- 然后配合队列q的信息进行父子节点对应弹出的操作，也就是说aux弹出一次，q中相应的弹出其对应的父子节点
- 最终返回建立好的树
方法一：递归
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
String Serialize(TreeNode root) {
if(root == null) return "#"; // 对所有的空节点也要存储占位符号"#"
return root.val + "," + Serialize(root.left) + "," + Serialize(root.right); // 递归前序遍历返回字符串
}
TreeNode Deserialize(String str) {
String[] s = str.split(","); // 切分字符串
Queue<String> q = new LinkedList<String>();
for(int i = 0; i != s.length; i++) q.offer(s[i]); // 将分割后的字符串数组顺序入队
return de(q); // 按照新的递归函数进行返回
}
TreeNode de(Queue<String> queue) {
String s = queue.poll(); // 递归函数每次从队首读出一个元素，因此读出的顺序也是前序
if(s.equals("#")) return null; // 对递归推出条件之一进行处理
TreeNode head = new TreeNode(Integer.valueOf(s)); // 前序首先建立一个节点
head.left = de(queue); // 然后递归左右子节点
head.right = de(queue);
return head;
}
}
复杂度分析
- 时间复杂度：，所有的节点都要遍历一遍
- 空间复杂度：，队列空间装载了所有节点的规模
方法二：迭代
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
String Serialize(TreeNode root) {
String res = "";
if(root == null) return "#!"; // 如果根节点为空，则按照我们的格式要求直接返回"#!"便于我们反序列化处理
Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 引入队列，准备进行层序遍历建立字符串
queue.offer(root); // 先压入根节点
while(!queue.isEmpty()) { // 队列不空的前提下循环
int n = queue.size(); // 获得该层的节点数量
while(n > 0) { // 对当前一整层进行处理
TreeNode p = queue.poll(); // 取出队首
if(p != null) { // 队首空和非空的处理不同
res = res + p.val + "!"; // 非空时，用节点值+分隔符续接字符串
queue.offer(p.left); // 左右子节点入队
queue.offer(p.right);
}
else res = res + "#!"; // 队首空，则用#填充并+分隔符续接字符串
n--; // 更新当前层中还未处理的节点个数
}
}
return res;
}
TreeNode Deserialize(String str) {
String[] s = str.split("!"); // 切分字符串
if(s[0].equals("#")) return null; // 特殊情况直接判断处理
Queue<String> q = new LinkedList<String>(); // 层序的节点排序结果存储在队列q中
Queue<TreeNode> aux = new LinkedList<TreeNode>(); // 引入aux辅助队列
for(int i = 0; i != s.length; i++) q.offer(s[i]); // 将分割后的字符串数组顺序入队
String cha_num = q.poll(); // 首先取出来一个字符
TreeNode root = new TreeNode(Integer.valueOf(cha_num)); // 将取出来的字符初始化节点对象
TreeNode head = root;
aux.offer(root); // aux队列也初始化完成
while(!q.isEmpty()) { // 看我们的q队列是否全部字符处理干净了
int n = aux.size(); // aux存储树的每一层节点，n表示该层的节点数量
while(n > 0) {
root = aux.poll(); // 每次取aux队首开始处理
if(root != null) { // 队首空和非空的处理是不同的
String a = q.poll(); // aux取出q中的元素并对象化后，q中存在字符串元素就是aux中这一层节点对应的下一层左右子节点，
String b = q.poll(); // 每一对取出来的a,b都是可以和aux当前队首完全对应上的
TreeNode l = a.equals("#") ? null : new TreeNode(Integer.valueOf(a)); // 判断a是否为#决定是否要建立一个新节点
TreeNode r = b.equals("#") ? null : new TreeNode(Integer.valueOf(b)); // 判断b是否为#决定是否要建立一个新节点
root.left = l; // 当前队首指向刚刚对象化的l子节点
root.right = r; // 当前队首指向刚刚对象化的r子节点
if(l != null) aux.offer(l); // 通过判断l是否为空，来控制是否要压入新节点，保证aux中每次取出来的队首节点可以对应上q队列中新元素
if(r != null) aux.offer(r); // 通过判断r是否为空，来控制是否要压入新节点，保证aux中每次取出来的队首节点可以对应上q队列中新元素
}
n--;
}
}
return head;
}
}
复杂度分析
- 时间复杂度：，所有的节点都要遍历一遍
- 空间复杂度：，队列空间装载了所有节点的规模
京公网安备 11010502036488号