1. 題目
描述
請實現兩個函數，分別用來序列化和反序列化二叉樹，不對序列化之后的字符串進行約束，但要求能夠根據序列化之后的字符串重新構造出一棵與原二叉樹相同的樹。
二叉樹的序列化(Serialize)是指：把一棵二叉樹按照某種遍歷方式的結果以某種格式保存為字符串，從而使得內存中建立起來的二叉樹可以持久保存。序列化可以基于先序、中序、后序、層序的二叉樹等遍歷方式來進行修改，序列化的結果是一個字符串，序列化時通過某種符號表示空節點（#）
二叉樹的反序列化(Deserialize)是指：根據某種遍歷順序得到的序列化字符串結果str，重構二叉樹。
例如，可以根據層序遍歷的方案序列化，如下圖:
層序序列化(即用函數Serialize轉化)如上的二叉樹轉為"{1,2,3,#,#,6,7}"，再能夠調用反序列化(Deserialize)將"{1,2,3,#,#,6,7}"構造成如上的二叉樹。
當然你也可以根據滿二叉樹結點位置的標號規律來序列化，還可以根據先序遍歷和中序遍歷的結果來序列化。不對序列化之后的字符串進行約束，所以歡迎各種奇思妙想。
數據范圍：節點數 n≤100，樹上每個節點的值滿足 0≤val≤150
要求：序列化和反序列化都是空間復雜度 O(n)，時間復雜度 O(n)
示例1
輸入：
{1,2,3,#,#,6,7}
返回值：
{1,2,3,#,#,6,7}
說明：
如題面圖 ? ?
示例2
輸入：
{8,6,10,5,7,9,11}
返回值：
{8,6,10,5,7,9,11}
2. 解題思路
本題分為兩部分，即二叉樹的序列化與反序列化。上一篇文章《可視化圖解算法36：序列化二叉樹-I》講解的是通過前序遍歷的方法完成二叉樹的序列化與反序列化，這一篇文章講解通過層序遍歷完成二叉樹的序列化與反序列化。
先來看二叉樹的序列化（將二叉樹序列化為字符串）：
可以看出二叉樹的節點值是通過層序遍歷的方式轉換為字符串的（空節點字符串為#），對于層序遍歷可以通過隊列來輔助完成（二叉樹層序遍歷詳細內容參考：《可視化圖解算法23：二叉樹的層序遍歷》）。具體思路為：
-
創建隊列，根節點入隊列；
-
節點出隊列，出隊列的節點值構成字符串，再將左右子樹入隊列；
注：左右子樹有可能為null，也需要入隊列。
-
左右子樹出隊列，出隊列的節點值構成字符串的字符，再將出隊列節點的左右子樹入隊列，如此循環往復。
再來看二叉樹的反序列化（將字符串轉換為二叉樹）：
二叉樹序列化的時候是通過層序遍歷的方法，反序列化的時候需要與此相對應（即也需要通過層序遍歷的思想完成）。具體思路為：
-
以逗號對字符串進行分割，將其轉換為數組；
-
基于層序遍歷的形式將數組中的字符串轉為二叉樹的節點并形成二叉樹：
節點出隊列，根據數組中的值創建左子樹（如果當前值是#，不創建左子樹），創建的左子樹再入隊列；根據數組中的值創建右子樹（如果當前值是#，不創建左子樹），創建的右子樹再入隊列；
-
依次循環，直至數組中的元素取完。
如果文字描述的不太清楚，你可以參考視頻的詳細講解。
-
Python編碼：嗶哩嗶哩_bilibili
https://www.bilibili.com/cheese/play/ep1372248 -
Java編碼：嗶哩嗶哩_bilibili
https://www.bilibili.com/cheese/play/ep1367356 -
Golang編碼：嗶哩嗶哩_bilibili
https://www.bilibili.com/cheese/play/ep1364781
3. 編碼實現
核心代碼如下：
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** @param root TreeNode類* @return TreeNode類*/
// Serialize 二叉樹序列化為字符串
func Serialize(root *TreeNode) string {// write code hereif root == nil {return "#"}// 1. 創建隊列并賦值queue := []*TreeNode{root}res := ""// 2. 操作隊列（二叉樹節點出隊列，左右子樹入隊列）for len(queue) > 0 {// 2.1 節點出隊列node := queue[0]queue = queue[1:]if node == nil { //null節點沒有葉子節點，不需要操作res += "#" + ","continue}res += strconv.Itoa(node.Val) + ","//2.2 左子樹入隊列queue = append(queue, node.Left)//2.3 右子樹入隊列queue = append(queue, node.Right)}res = strings.TrimRight(res[:len(res)-1], ",#") //去掉末尾連續的" ,# "return res
}// Deserialize 字符串反序列化為二叉樹
func Deserialize(s string) *TreeNode {// write code hereif s == "#" || strings.TrimSpace(s) == "" {return nil}// 1. 分割（序列化的）字符串arr := strings.Split(s, ",")// 2. 創建root節點rootVal, _ := strconv.Atoi(arr[0])root := &TreeNode{Val: rootVal}// 3. 操作隊列（二叉樹節點出隊列，左右子樹入隊列）queue := []*TreeNode{root}index := 1 // arr對應的索引for index < len(arr) {// 3.1 節點出隊列node := queue[0] // 隊列的頭節點queue = queue[1:] // 刪除隊列的頭節點// 3.2 創建左子樹并入隊列if arr[index] != "#" {leftVal, _ := strconv.Atoi(arr[index])node.Left = &TreeNode{Val: leftVal}queue = append(queue, node.Left) //添加左子樹到隊列}index++ // 移動索引（不管左子樹用到了#還是數值，都需要移動index）// 3.3 創建右子樹并入隊列if index < len(arr) && arr[index] != "#" {rightVal, _ := strconv.Atoi(arr[index])node.Right = &TreeNode{Val: rightVal}queue = append(queue, node.Right) // 添加右子樹到隊列}index++ // 移動索引的值（不管右子樹用到了#還是數值，都需要移動index）}return root
}
具體完整代碼你可以參考下面視頻的詳細講解。具體完整代碼你可以參考下面視頻的詳細講解。-
Python編碼：數據結構筆試面試算法-Python語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Python語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕
https://www.bilibili.com/cheese/play/ep1372248 -
Java編碼：嗶哩嗶哩_bilibili
https://www.bilibili.com/cheese/play/ep1367356 -
Golang編碼：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕
https://www.bilibili.com/cheese/play/ep1364781
4.小結
二叉樹的序列化與反序列化可以通過層序遍歷的方法來完成，層序遍歷可以通過隊列來輔助完成。
《數據結構與算法》深度精講課程正式上線啦！七大核心算法模塊全解析：
?????????? ?鏈表
?????????? ?二叉樹
?????????? ?二分查找、排序
?????????? ?堆、棧、隊列
?????????? ?回溯算法
?????????? ?哈希算法
?????????? ?動態規劃
無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建扎實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！
-
Python編碼實現：數據結構筆試面試算法-Python語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Python語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕
https://www.bilibili.com/cheese/play/ss897667807 -
Java編碼實現：數據結構筆試面試算法-Java語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Java語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕
https://www.bilibili.com/cheese/play/ss161443488 -
Golang編碼實現：嗶哩嗶哩_bilibili
https://www.bilibili.com/cheese/play/ss63997
對于二叉樹的相關算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。
今日佳句：百川東到海，何時復西歸？
)
