序列化操作步骤
- 首先，我们要明确一个目标----经过序列化，我们最终想要得到一棵什么样的树？这个问题相当重要！！！相当重要！！！相当重要！！！它是整道题的核心！！！只有想清楚了这个问题，我们才能实现序列化和反序列化操作！！！
- 在这里呢，我想通过广度优先遍历实现一棵完全二叉树。注意，是完全二叉树！！！无论题目输入的是什么类型的树，我们统一将它构造成完全二叉树！！！
- 为什么呢？我不构造完全二叉树可以吗？当然可以啦！但是呢，我个人认为，完全二叉树的反序列化会简单很多！！！所以，我构造完全二叉树！！！
具体代码实现如下：(代码里有很详细的注释)
String Serialize(TreeNode root) {
// 一些特殊情况的处理
if (null == root) { // 如果根节点为空，直接返回一个空串
return "";
}
if (null == root.left && null == root.right) { // 如果左右子树都为空，直接返回根节点
return root.val + "";
}
// 首先，我们要明确一个目标----经过序列化，我们最终想要得到一棵什么样的树？这个问题相当重要！！！相当重要！！！相当重要！！！它是整道题的核心！！！只有想清楚了这个问题，我们才能实现序列化和反序列化操作！！！
// 在这里呢，我想通过广度优先遍历实现一棵完全二叉树。注意，是完全二叉树！！！无论题目输入的是什么类型的树，我们统一将它构造成完全二叉树！！！
// 为什么呢？我不构造完全二叉树可以吗？当然可以啦！但是呢，我个人认为，完全二叉树的反序列化会简单很多！！！所以，我构造完全二叉树！！！
// 具体代码实现如下：
// 首先，我们通过广度优先遍历，找到这棵树中的最后一个节点(这一步挺重要的，是后面构造完全二叉树过程的终止条件)
Stack<TreeNode> stack = new Stack<>(); // 定义一个辅助栈，用于存放广度优先遍历的结果
LinkedList<TreeNode> queue = new LinkedList<>(); // 定义一个队列(广度优先遍历的好帮手)
TreeNode tmp = root; // 定义一个辅助节点，初始时指向 root 节点
queue.add(tmp); // 初始时，先将 root 节点入队列
// 以下这一小段代码就是很普通的广度优先遍历过程，相信大家都很熟悉了
while (!queue.isEmpty()) {
tmp = queue.poll();
stack.push(tmp); // 这里我们将出队列的节点压入到栈中
// 先左再右，顺序别搞反了
if (null != tmp.left) {
queue.add(tmp.left);
}
if (null != tmp.right) {
queue.add(tmp.right);
}
}
// 此时，栈顶元素就是我们要的整棵树的最后一个节点
TreeNode endNode = stack.pop();
// 有了这么一个节点之后，我们就可以通过广度优先遍历算法，构造出一棵完全二叉树啦！
tmp = root; // 将辅助节点重新指向根节点
String str = ""; // 定义一个空串，用于存放最终的遍历结果
queue.add(tmp); // 初始时，先将 root 节点入队列
// 以下这段代码，本质上就是广度优先遍历，但是稍微有所不同，说明如下：
// 1）由于我们要构造的是一棵完全二叉树，所以，当我们获取到的某个节点的左孩子或者是右孩子为空时，我们就以 null 来代替它的那个空的孩子节点。换句话说，即使它的孩子为空，我们一样要将这个孩子入队列，只不过是以 null 的方式入队列。
// 2）由于 null 的存在，每出队一个节点，我们都要先判断它是否为 null。如果为 null，我们就直接就以 # 来替代这个节点，然后直接跳出此次循环。
// 注意，重点来了，哪怕该节点为 null，我们一样认为它有左右孩子节点，只不过它的左右孩子节点都为 null！！！千万记住了，这是构造完全二叉树中很重要的一步！！！
// 3）如果出队的节点不为 null，我们还要判断它是否是最后一个节点。如果是最后一个节点，我们就跳出循环。
// 注意，这一步也很重要！！！如果没有这一步，整个循环会陷入死循环。原因就是，队列中永远会存在 null 这么一个对象。而之所以会永远存在 null，是因为 2）这一步骤造成的！！！
// 4）别忘了，节点与节点之间通过 , 进行分割。
while (!queue.isEmpty()) {
tmp = queue.poll(); // 出队一个节点
if (null == tmp) { // 如果这个节点为 null
str += "#,";
queue.add(null);
queue.add(null);
continue; // 跳出 当次 循环
}
else { // 如果这个节点不为 null
if (tmp == endNode) { // 如果这个节点是整棵树的最后一个节点
str += endNode.val; // 记得，最后一个节点不用再添加一个 , 了
break; // 跳出循环
}
else {
str = str + tmp.val + ","; // 别忘了添加 , 用于分割节点
}
}
if (null != tmp.left) {
queue.add(tmp.left); // 如果左孩子不为空，入队
}
else {
queue.add(null); // 如果左孩子为空，将 null 入队
}
// 右孩子同上操作
if (null != tmp.right) {
queue.add(tmp.right);
}
else {
queue.add(null);
}
}
// 最终，我们得到了一棵完全二叉树的序列化结果
return str;
}
反序列化操作
由于我们构造了一棵完全二叉树，所以反序列化操作就简单很多。
一般来说，我们可以使用数组存放一棵完全二叉树。这里有些性质要知道(我们假设每个节点当前的下标为 i)：
- 对于当前节点 i 来说，它的父节点的下标为 (i-1)/2 这个性质对于根节点一样适用，根节点的父亲就是它自己嘛。
- 对于当前节点 i 来说，它的左孩子的下标为 (2i+1) ，右孩子节点的下标为 (2i+2) 注意，这里有个前提，数组下标不要越界。
清楚了以上几点性质之后，我们就可以开始实现反序列化操作了。
具体代码实现如下：(代码里有很详细的注释)
TreeNode Deserialize(String str) {
// 一些特殊情况的处理
if (0 == str.length()) { // 如果 String 字符串的长度为 0，那么直接返回一个空节点
return null;
}
if (1 == str.length()) { // 如果 String 字符串的长度为 1，直接返回根节点
return new TreeNode(Integer.valueOf(str));
}
// 由于我们构造了一棵完全二叉树，所以反序列化操作就简单很多。
// 一般来说，我们可以使用数组存放一棵完全二叉树。这里有些性质要知道(我们假设每个节点当前的下标为 i)：
// 1）对于当前节点 i 来说，它的父节点的下标为 (i-1)/2 这个性质对于根节点一样适用，根节点的父亲就是它自己嘛。
// 2）对于当前节点 i 来说，它的左孩子的下标为 (2i+1) ，右孩子节点的下标为 (2i+2) 注意，这里有个前提，数组下标不要越界。
// 清楚了以上几点性质之后，我们就可以开始实现反序列化操作了。
String[] strs = str.split(","); // 首先，我们将字符串按照 , 进行分割。分割后的每一个 String，代表了一个节点(# 表示的是空节点)
ArrayList<TreeNode> list = new ArrayList<>(); // 定义一个 ArrayList 数组，用于存放完全二叉树
// 遍历 strs 数组，将每个 String 元素创建成一个 TreeNode 节点，并添加到 ArrayList 数组中去
// 这里有一点需要说明一下，即使是空节点，我们一样要为它创建一个 TreeNode，这个 TreeNode 的 val 值为 -1(题目说每个节点的值 0 <= val <= 150。我们这里规定，负数就代表为空节点)
for (String ts : strs) {
if ("#".equals(ts)) {
list.add(new TreeNode(-1));
}
else {
list.add(new TreeNode(Integer.valueOf(ts)));
}
}
// 此时，ArrayList 就存放了一棵完全二叉树。然后，我们就可以通过遍历这个 ArrayList，反序列化出一棵二叉树了(注意，不是完全二叉树了！！！空节点我们不再保留！！！)
TreeNode root = list.get(0); // 获取根节点(就是 ArrayList 数组中下标为 0 的元素)
TreeNode tmp = null; // 定义一个辅助节点
TreeNode fa = null; // 定义一个辅助节点，用于存放的是下标为 i 的节点的父节点
// 遍历 ArrayList 数组。这里有一点需要注意，我们要从数组的尾部往头部遍历，防止数组角标越界！！！同时，我们不需要遍历到根节点，因为根节点的父节点就是它自己！！！
for (int i = list.size() - 1; i > 0; i--) {
tmp = list.get(i);
if (tmp.val == -1) { // 如果当前节点的 val 值为 -1，我们就认为这是一个空节点，直接跳过 当次 循环
continue;
}
else {
fa = list.get((i - 1) / 2); // 如果当前节点的 val 值不为 -1，我们就通过下标找到这个节点的父节点，然后让这个节点和它的父节点建立连接
if (i % 2 != 0) { // 当前节点为它父节点的左孩子
fa.left = tmp;
}
else { // 当前节点为它父节点的右孩子
fa.right = tmp;
}
}
}
return root;
}
}
整道题的完整代码如下：
import java.util.LinkedList;
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
// 序列化操作
String Serialize(TreeNode root) {
// 一些特殊情况的处理
if (null == root) { // 如果根节点为空，直接返回一个空串
return "";
}
if (null == root.left && null == root.right) { // 如果左右子树都为空，直接返回根节点
return root.val + "";
}
// 首先，我们要明确一个目标----经过序列化，我们最终想要得到一棵什么样的树？这个问题相当重要！！！相当重要！！！相当重要！！！它是整道题的核心！！！只有想清楚了这个问题，我们才能实现序列化和反序列化操作！！！
// 在这里呢，我想通过广度优先遍历实现一棵完全二叉树。注意，是完全二叉树！！！无论题目输入的是什么类型的树，我们统一将它构造成完全二叉树！！！
// 为什么呢？我不构造完全二叉树可以吗？当然可以啦！但是呢，我个人认为，完全二叉树的反序列化会简单很多！！！所以，我构造完全二叉树！！！
// 具体代码实现如下：
// 首先，我们通过广度优先遍历，找到这棵树中的最后一个节点(这一步挺重要的，是后面构造完全二叉树过程的终止条件)
Stack<TreeNode> stack = new Stack<>(); // 定义一个辅助栈，用于存放广度优先遍历的结果
LinkedList<TreeNode> queue = new LinkedList<>(); // 定义一个队列(广度优先遍历的好帮手)
TreeNode tmp = root; // 定义一个辅助节点，初始时指向 root 节点
queue.add(tmp); // 初始时，先将 root 节点入队列
// 以下这一小段代码就是很普通的广度优先遍历过程，相信大家都很熟悉了
while (!queue.isEmpty()) {
tmp = queue.poll();
stack.push(tmp); // 这里我们将出队列的节点压入到栈中
// 先左再右，顺序别搞反了
if (null != tmp.left) {
queue.add(tmp.left);
}
if (null != tmp.right) {
queue.add(tmp.right);
}
}
// 此时，栈顶元素就是我们要的整棵树的最后一个节点
TreeNode endNode = stack.pop();
// 有了这么一个节点之后，我们就可以通过广度优先遍历算法，构造出一棵完全二叉树啦！
tmp = root; // 将辅助节点重新指向根节点
String str = ""; // 定义一个空串，用于存放最终的遍历结果
queue.add(tmp); // 初始时，先将 root 节点入队列
// 以下这段代码，本质上就是广度优先遍历，但是稍微有所不同，说明如下：
// 1）由于我们要构造的是一棵完全二叉树，所以，当我们获取到的某个节点的左孩子或者是右孩子为空时，我们就以 null 来代替它的那个空的孩子节点。换句话说，即使它的孩子为空，我们一样要将这个孩子入队列，只不过是以 null 的方式入队列。
// 2）由于 null 的存在，每出队一个节点，我们都要先判断它是否为 null。如果为 null，我们就直接就以 # 来替代这个节点，然后直接跳出此次循环。
// 注意，重点来了，哪怕该节点为 null，我们一样认为它有左右孩子节点，只不过它的左右孩子节点都为 null！！！千万记住了，这是构造完全二叉树中很重要的一步！！！
// 3）如果出队的节点不为 null，我们还要判断它是否是最后一个节点。如果是最后一个节点，我们就跳出循环。
// 注意，这一步也很重要！！！如果没有这一步，整个循环会陷入死循环。原因就是，队列中永远会存在 null 这么一个对象。而之所以会永远存在 null，是因为 2）这一步骤造成的！！！
// 4）别忘了，节点与节点之间通过 , 进行分割。
while (!queue.isEmpty()) {
tmp = queue.poll(); // 出队一个节点
if (null == tmp) { // 如果这个节点为 null
str += "#,";
queue.add(null);
queue.add(null);
continue; // 跳出 当次 循环
}
else { // 如果这个节点不为 null
if (tmp == endNode) { // 如果这个节点是整棵树的最后一个节点
str += endNode.val; // 记得，最后一个节点不用再添加一个 , 了
break; // 跳出循环
}
else {
str = str + tmp.val + ","; // 别忘了添加 , 用于分割节点
}
}
if (null != tmp.left) {
queue.add(tmp.left); // 如果左孩子不为空，入队
}
else {
queue.add(null); // 如果左孩子为空，将 null 入队
}
// 右孩子同上操作
if (null != tmp.right) {
queue.add(tmp.right);
}
else {
queue.add(null);
}
}
// 最终，我们得到了一棵完全二叉树的序列化结果
return str;
}
// 反序列化操作
TreeNode Deserialize(String str) {
// 一些特殊情况的处理
if (0 == str.length()) { // 如果 String 字符串的长度为 0，那么直接返回一个空节点
return null;
}
if (1 == str.length()) { // 如果 String 字符串的长度为 1，直接返回根节点
return new TreeNode(Integer.valueOf(str));
}
// 由于我们构造了一棵完全二叉树，所以反序列化操作就简单很多。
// 一般来说，我们可以使用数组存放一棵完全二叉树。这里有些性质要知道(我们假设每个节点当前的下标为 i)：
// 1）对于当前节点 i 来说，它的父节点的下标为 (i-1)/2 这个性质对于根节点一样适用，根节点的父亲就是它自己嘛。
// 2）对于当前节点 i 来说，它的左孩子的下标为 (2i+1) ，右孩子节点的下标为 (2i+2) 注意，这里有个前提，数组下标不要越界。
// 清楚了以上几点性质之后，我们就可以开始实现反序列化操作了。
String[] strs = str.split(","); // 首先，我们将字符串按照 , 进行分割。分割后的每一个 String，代表了一个节点(# 表示的是空节点)
ArrayList<TreeNode> list = new ArrayList<>(); // 定义一个 ArrayList 数组，用于存放完全二叉树
// 遍历 strs 数组，将每个 String 元素创建成一个 TreeNode 节点，并添加到 ArrayList 数组中去
// 这里有一点需要说明一下，即使是空节点，我们一样要为它创建一个 TreeNode，这个 TreeNode 的 val 值为 -1(题目说每个节点的值 0 <= val <= 150。我们这里规定，负数就代表为空节点)
for (String ts : strs) {
if ("#".equals(ts)) {
list.add(new TreeNode(-1));
}
else {
list.add(new TreeNode(Integer.valueOf(ts)));
}
}
// 此时，ArrayList 就存放了一棵完全二叉树。然后，我们就可以通过遍历这个 ArrayList，反序列化出一棵二叉树了(注意，不是完全二叉树了！！！空节点我们不再保留！！！)
TreeNode root = list.get(0); // 获取根节点(就是 ArrayList 数组中下标为 0 的元素)
TreeNode tmp = null; // 定义一个辅助节点
TreeNode fa = null; // 定义一个辅助节点，用于存放的是下标为 i 的节点的父节点
// 遍历 ArrayList 数组。这里有一点需要注意，我们要从数组的尾部往头部遍历，防止数组角标越界！！！同时，我们不需要遍历到根节点，因为根节点的父节点就是它自己！！！
for (int i = list.size() - 1; i > 0; i--) {
tmp = list.get(i);
if (tmp.val == -1) { // 如果当前节点的 val 值为 -1，我们就认为这是一个空节点，直接跳过 当次 循环
continue;
}
else {
fa = list.get((i - 1) / 2); // 如果当前节点的 val 值不为 -1，我们就通过下标找到这个节点的父节点，然后让这个节点和它的父节点建立连接
if (i % 2 != 0) { // 当前节点为它父节点的左孩子
fa.left = tmp;
}
else { // 当前节点为它父节点的右孩子
fa.right = tmp;
}
}
}
return root;
}
}
京公网安备 11010502036488号