?
目錄
1、題目介紹
2、解題思路?
2.1、詳細過程圖解
2.2、代碼描述?
?2.3、完整代碼
?
1、題目介紹
原題鏈接：297. 二叉樹的序列化與反序列化 - 力扣（LeetCode）
?示例 1：
輸入：root = [1,2,3,null,null,4,5]
輸出：[1,2,3,null,null,4,5]
示例 2：
輸入：root = [ ]
輸出：[ ]
示例 3：
輸入：root = [1]
輸出：[1]
示例 4：
輸入：root = [1,2]
輸出：[1,2]
提示：
- 樹中結點數在范圍?
[0, 104]?內 -1000 <= Node.val <= 1000
2、解題思路?
二叉樹序列化就是將內存中的二叉樹變成硬盤中的字符串形式，并且要求每個二叉樹能夠對應一個唯一的字符串。
二叉樹反序列化就是將這個唯一字符串在內存中還原回對應的二叉樹。
2.1、詳細過程圖解
這里采用先序遍歷完成序列化。只要理解了一種遍歷的序列化，其他遍歷（包括不限于中序遍歷、后序遍歷、層次遍歷）的序列化都是依葫蘆畫瓢了。
先說規(guī)則：
- 通過先序遍歷的順序進行訪問二叉樹，假如訪問到結點1，就將1寫入字符串中，同理結點2就是寫入2到節(jié)點中
- 如果遇到空結點則在字符串中存入一個標識符號，這里我采用井號 # 來表述空結點。
- 同時兩個節(jié)點之間需要使用下劃線?_ 隔開，也可以理解為表示一個結點值的結束。
序列化過程圖解：
開始時字符串str為空。按照先序遍歷，首先是訪問結點1，所以此時字符串中存入了1和表示結點值結束的下劃線 _。
str[ ]= "1_"
接著先序遍歷訪問到結點2，繼續(xù)將2和下劃線_拼接進字符串str中。
str[ ]= "1_2_"
接著先序遍歷訪問到空結點，此時將表示空姐點的標識符號井號#下劃線_拼接進字符串str中。
str[ ]= "1_2_#_"
同理依次進行遍歷
str[ ]= "1_2_#_#_"
通過依次遍歷最后得到str字符串
str[ ]= "1_2_#_#_3_4_#_#_5_#_#_"
這個str字符串即為二叉樹的序列化，而用字符串通過先序遍歷還原回二叉樹就成為反序列化。
反序列化過程圖解：
str從前往后遍歷，按照先序遍歷【頭左右】的順序還原回二叉樹。
?
?
?依次遍歷str最終完成還原回原二叉樹。
?
2.2、代碼描述?
使用遞歸將二叉樹按照先序遍歷生成對應的序列化字符串ret。
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) //等于空時返回井號標識符
{
return "#_";
}
String res = root.val + "_"; //將結點值與下劃線_拼接
res += serialize(root.left); //將左子樹返回的字符串拼接到當前的ret后
res += serialize(root.right); //將右子樹返回的字符串拼接到當前的ret后
return ret;
}使用split方法對字符串進行拆分，拆分出來的值放入一個數組中，再用隊列依次接收數組的 值。
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] val = data.split("_"); //將data字符串按照下劃線_為分隔符對字符串進行拆分
Queue<String> queue = new LinkedList<>(); //隊列
for(int i = 0;i < val.length; i++)
{
queue.add(val[i]); //將拆分出來的值依次入隊
}
return reconPreOrder(queue); //返回隊列
}將得到的隊列依次出隊，通過遞歸判斷是否為空標識符井號#，是則返回null，否則將值存入新開辟的頭結點root中，再通過遞歸方式創(chuàng)建左子樹以及右子樹。最后將頭結點root返回，即完成二叉樹的反序列化。
public static TreeNode reconPreOrder(Queue<String> queue)
{
String val = queue.poll(); //出隊
if(val.equals("#")) //等于#則返回null
{
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(val)); //創(chuàng)建頭結點存放val值
root.left = reconPreOrder(queue); //從遞歸中獲取左子樹信息
root.right = reconPreOrder(queue); //從遞歸中獲取右子樹信息
return root; //最后返回頭結點
}?2.3、完整代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
{
return "#_";
}
String res = root.val + "_";
res += serialize(root.left);
res += serialize(root.right);
return res;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] val = data.split("_");
Queue<String> queue = new LinkedList<>();
for(int i = 0;i < val.length; i++)
{
queue.add(val[i]);
}
return reconPreOrder(queue);
}
public static TreeNode reconPreOrder(Queue<String> queue)
{
String val = queue.poll();
if(val.equals("#"))
{
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(val));
root.left = reconPreOrder(queue);
root.right = reconPreOrder(queue);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
彩蛋：
在查看其他題解時發(fā)現了一個有趣的解題方法（請勿模仿）哈哈哈哈哈
?
?
關于二叉樹遍歷的精講：
【算法與數據結構】二叉樹的三種遍歷代碼實現（上）—— 用遞歸序知識點講解_Hacynn的博客-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5502【算法與數據結構】二叉樹的三種遍歷代碼實現（下）—— 非遞歸方式實現（大量圖解）-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133669283?spm=1001.2014.3001.5502
?
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！文章來源地址http://www.zghlxwxcb.cn/news/detail-713948.html
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！文章來源：http://www.zghlxwxcb.cn/news/detail-713948.html
如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！
到了這里，關于【LeetCode力扣】297. 二叉樹的序列化與反序列化的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
