一文帶你看懂二叉樹的序列化
點(diǎn)擊藍(lán)色“力扣加加”關(guān)注我喲
加個(gè)“星標(biāo)”，帶你揭開算法的神秘面紗！
?這是力扣加加第「11」篇原創(chuàng)文章
?
我們先來看下什么是序列化，以下定義來自維基百科：
?序列化（serialization）在計(jì)算機(jī)科學(xué)的數(shù)據(jù)處理中，是指將數(shù)據(jù)結(jié)構(gòu)或?qū)ο鬆顟B(tài)轉(zhuǎn)換成可取用格式（例如存成文件，存于緩沖，或經(jīng)由網(wǎng)絡(luò)中發(fā)送），以留待后續(xù)在相同或另一臺計(jì)算機(jī)環(huán)境中，能恢復(fù)原先狀態(tài)的過程。依照序列化格式重新獲取字節(jié)的結(jié)果時(shí)，可以利用它來產(chǎn)生與原始對象相同語義的副本。對于許多對象，像是使用大量引用的復(fù)雜對象，這種序列化重建的過程并不容易。面向?qū)ο笾械膶ο笮蛄谢?，并不概括之前原始對象所關(guān)系的函數(shù)。這種過程也稱為對象編組（marshalling）。從一系列字節(jié)提取數(shù)據(jù)結(jié)構(gòu)的反向操作，是反序列化（也稱為解編組、deserialization、unmarshalling）。
?
可見，序列化和反序列化在計(jì)算機(jī)科學(xué)中的應(yīng)用還是非常廣泛的。就拿 LeetCode 平臺來說，其允許用戶輸入形如：
[1,2,3,null,null,4,5]
這樣的數(shù)據(jù)結(jié)構(gòu)來描述一顆樹：
([1,2,3,null,null,4,5] 對應(yīng)的二叉樹)
其實(shí)序列化和反序列化只是一個(gè)概念，不是一種具體的算法，而是很多的算法。并且針對不同的數(shù)據(jù)結(jié)構(gòu)，算法也會不一樣。本文主要講述的是二叉樹的序列化和反序列化?？赐瓯疚闹?，你就可以放心大膽地去 AC 以下兩道題：
449. 序列化和反序列化二叉搜索樹(中等) 297. 二叉樹的序列化與反序列化(困難)
前置知識
閱讀本文之前，需要你對樹的遍歷以及 BFS 和 DFS 比較熟悉。如果你還不熟悉，推薦閱讀一下相關(guān)文章之后再來看。或者我這邊也寫了一個(gè)總結(jié)性的文章二叉樹的遍歷，你也可以看看。
前言
我們知道：二叉樹的深度優(yōu)先遍歷，根據(jù)訪問根節(jié)點(diǎn)的順序不同，可以將其分為前序遍歷，中序遍歷,?后序遍歷。即如果先訪問根節(jié)點(diǎn)就是前序遍歷，最后訪問根節(jié)點(diǎn)就是后續(xù)遍歷，其它則是中序遍歷。而左右節(jié)點(diǎn)的相對順序是不會變的，一定是先左后右。
?當(dāng)然也可以設(shè)定為先右后左。
?
并且知道了三種遍歷結(jié)果中的任意兩種即可還原出原有的樹結(jié)構(gòu)。這不就是序列化和反序列化么？如果對這個(gè)比較陌生的同學(xué)建議看看我之前寫的《構(gòu)造二叉樹系列》
有了這樣一個(gè)前提之后算法就自然而然了。即先對二叉樹進(jìn)行兩次不同的遍歷，不妨假設(shè)按照前序和中序進(jìn)行兩次遍歷。然后將兩次遍歷結(jié)果序列化，比如將兩次遍歷結(jié)果以逗號“,” join 成一個(gè)字符串。之后將字符串反序列即可，比如將其以逗號“,” split 成一個(gè)數(shù)組。
序列化：
class?Solution:
????def?preorder(self,?root:?TreeNode):
????????if?not?root:?return?[]
????????return?[str(root.val)]?+self.?preorder(root.left)?+?self.preorder(root.right)
????def?inorder(self,?root:?TreeNode):
????????if?not?root:?return?[]
????????return??self.inorder(root.left)?+?[str(root.val)]?+?self.inorder(root.right)
????def?serialize(self,?root):
????????ans?=?''
????????ans?+=?','.join(self.preorder(root))
????????ans?+=?'$'
????????ans?+=?','.join(self.inorder(root))
????????return?ans
反序列化：
這里我直接用了力扣?105. 從前序與中序遍歷序列構(gòu)造二叉樹?的解法，一行代碼都不改。
class?Solution:
????def?deserialize(self,?data:?str):
????????preorder,?inorder?=?data.split('$')
????????if?not?preorder:?return?None
????????return?self.buildTree(preorder.split(','),?inorder.split(','))
????def?buildTree(self,?preorder:?List[int],?inorder:?List[int])?->?TreeNode:
????????#?實(shí)際上inorder?和?preorder?一定是同時(shí)為空的，因此你無論判斷哪個(gè)都行
????????if?not?preorder:
????????????return?None
????????root?=?TreeNode(preorder[0])
????????i?=?inorder.index(root.val)
????????root.left?=?self.buildTree(preorder[1:i?+?1],?inorder[:i])
????????root.right?=?self.buildTree(preorder[i?+?1:],?inorder[i+1:])
????????return?root
實(shí)際上這個(gè)算法是不一定成立的，原因在于樹的節(jié)點(diǎn)可能存在重復(fù)元素。也就是說我前面說的知道了三種遍歷結(jié)果中的任意兩種即可還原出原有的樹結(jié)構(gòu)是不對的，嚴(yán)格來說應(yīng)該是「如果樹中不存在重復(fù)的元素，那么知道了三種遍歷結(jié)果中的任意兩種即可還原出原有的樹結(jié)構(gòu)」。
聰明的你應(yīng)該發(fā)現(xiàn)了，上面我的代碼用了?i = inorder.index(root.val)，如果存在重復(fù)元素，那么得到的索引 i 就可能不是準(zhǔn)確的。但是，如果題目限定了沒有重復(fù)元素則可以用這種算法。但是現(xiàn)實(shí)中不出現(xiàn)重復(fù)元素不太現(xiàn)實(shí)，因此需要考慮其他方法。那究竟是什么樣的方法呢? 接下來進(jìn)入正題。
DFS
序列化
我們來模仿一下力扣的記法。比如：[1,2,3,null,null,4,5](本質(zhì)上是 BFS 層次遍歷)，對應(yīng)的樹如下：
?選擇這種記法，而不是 DFS 的記法的原因是看起來比較直觀
?
序列化的代碼非常簡單， 我們只需要在普通的遍歷基礎(chǔ)上，增加對空節(jié)點(diǎn)的輸出即可（普通的遍歷是不處理空節(jié)點(diǎn)的）。
比如我們都樹進(jìn)行一次前序遍歷的同時(shí)增加空節(jié)點(diǎn)的處理。選擇前序遍歷的原因是容易知道根節(jié)點(diǎn)的位置，并且代碼好寫，不信你可以試試。
因此序列化就僅僅是普通的 DFS 而已，直接給大家看看代碼。
Python 代碼：
class?Codec:
????def?serialize_dfs(self,?root,?ans):
????????#?空節(jié)點(diǎn)也需要序列化，否則無法唯一確定一棵樹，后不贅述。
????????if?not?root:?return?ans?+?'#,'
????????#?節(jié)點(diǎn)之間通過逗號（,）分割
????????ans?+=?str(root.val)?+?','
????????ans?=?self.serialize_dfs(root.left,?ans)
????????ans?=?self.serialize_dfs(root.right,?ans)
????????return?ans
????def?serialize(self,?root):
????????#?由于最后會添加一個(gè)額外的逗號，因此需要去除最后一個(gè)字符，后不贅述。
????????return?self.serialize_dfs(root,?'')[:-1]
Java 代碼：
public?class?Codec?{
????public?String?serialize_dfs(TreeNode?root,?String?str)?{
????????if?(root?==?null)?{
????????????str?+=?"None,";
????????}?else?{
????????????str?+=?str.valueOf(root.val)?+?",";
????????????str?=?serialize_dfs(root.left,?str);
????????????str?=?serialize_dfs(root.right,?str);
????????}
????????return?str;
????}
????public?String?serialize(TreeNode?root)?{
????????return?serialize_dfs(root,?"");
????}
}
[1,2,3,null,null,4,5]?會被處理為1,2,#,#,3,4,#,#,5,#,#
我們先看一個(gè)短視頻：
（動畫來自力扣）
反序列化
反序列化的第一步就是將其展開。以上面的例子來說，則會變成數(shù)組：[1,2,#,#,3,4,#,#,5,#,#]，然后我們同樣執(zhí)行一次前序遍歷，每次處理一個(gè)元素，重建即可。由于我們采用的前序遍歷，因此第一個(gè)是根元素，下一個(gè)是其左子節(jié)點(diǎn)，下下一個(gè)是其右子節(jié)點(diǎn)。
Python 代碼：
????def?deserialize_dfs(self,?nodes):
????????if?nodes:
????????????if?nodes[0]?==?'#':
????????????????nodes.pop(0)
????????????????return?None
????????????root?=?TreeNode(nodes.pop(0))
????????????root.left?=?self.deserialize_dfs(nodes)
????????????root.right?=?self.deserialize_dfs(nodes)
????????????return?root
????????return?None
????def?deserialize(self,?data:?str):
????????nodes?=?data.split(',')
????????return?self.deserialize_dfs(nodes)
Java 代碼：
????public?TreeNode?deserialize_dfs(List?l) ?{
????????if?(l.get(0).equals("None"))?{
????????????l.remove(0);
????????????return?null;
????????}
????????TreeNode?root?=?new?TreeNode(Integer.valueOf(l.get(0)));
????????l.remove(0);
????????root.left?=?deserialize_dfs(l);
????????root.right?=?deserialize_dfs(l);
????????return?root;
????}
????public?TreeNode?deserialize(String?data)?{
????????String[]?data_array?=?data.split(",");
????????List?data_list?=?new?LinkedList(Arrays.asList(data_array));
????????return?deserialize_dfs(data_list);
????}
「復(fù)雜度分析」
時(shí)間復(fù)雜度：每個(gè)節(jié)點(diǎn)都會被處理一次，因此時(shí)間復(fù)雜度為?，其中??為節(jié)點(diǎn)的總數(shù)。 空間復(fù)雜度：空間復(fù)雜度取決于棧深度，因此空間復(fù)雜度為?，其中??為樹的深度。
BFS
序列化
實(shí)際上我們也可以使用 BFS 的方式來表示一棵樹。在這一點(diǎn)上其實(shí)就和力扣的記法是一致的了。
我們知道層次遍歷的時(shí)候?qū)嶋H上是有層次的。只不過有的題目需要你記錄每一個(gè)節(jié)點(diǎn)的層次信息，有些則不需要。
這其實(shí)就是一個(gè)樸實(shí)無華的 BFS，唯一不同則是增加了空節(jié)點(diǎn)。
Python 代碼：
class?Codec:
????def?serialize(self,?root):
????????ans?=?''
????????queue?=?[root]
????????while?queue:
????????????node?=?queue.pop(0)
????????????if?node:
????????????????ans?+=?str(node.val)?+?','
????????????????queue.append(node.left)
????????????????queue.append(node.right)
????????????else:
????????????????ans?+=?'#,'
????????return?ans[:-1]
反序列化
如圖有這樣一棵樹：
那么其層次遍歷為 [1,2,3,#,#, 4, 5]。我們根據(jù)此層次遍歷的結(jié)果來看下如何還原二叉樹，如下是我畫的一個(gè)示意圖：
容易看出：
level x 的節(jié)點(diǎn)一定指向 level x + 1 的節(jié)點(diǎn)，如何找到 level + 1 呢？這很容易通過層次遍歷來做到。 對于給的的 level x，從左到右依次對應(yīng) level x + 1 的節(jié)點(diǎn)，即第 1 個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)對應(yīng)下一層的第 1 個(gè)和第 2 個(gè)節(jié)點(diǎn)，第 2 個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)對應(yīng)下一層的第 3 個(gè)和第 4 個(gè)節(jié)點(diǎn)。。。 接上，其實(shí)如果你仔細(xì)觀察的話，實(shí)際上 level x 和 level x + 1 的判斷是無需特別判斷的。我們可以把思路逆轉(zhuǎn)過來： 即第 1 個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)對應(yīng)第 1 個(gè)和第 2 個(gè)節(jié)點(diǎn)，第 2 個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)對應(yīng)第 3 個(gè)和第 4 個(gè)節(jié)點(diǎn)。。。（注意，沒了下一層三個(gè)字）
因此我們的思路也是同樣的 BFS，并依次連接左右節(jié)點(diǎn)。
Python 代碼：
????def?deserialize(self,?data:?str):
????????if?data?==?'#':?return?None
????????#?數(shù)據(jù)準(zhǔn)備
????????nodes?=?data.split(',')
????????if?not?nodes:?return?None
????????#?BFS
????????root?=?TreeNode(nodes[0])
????????queue?=?[root]
????????#?已經(jīng)有?root?了，因此從?1?開始
????????i?=?1
????????while?i?1:
????????????node?=?queue.pop(0)
????????????#
????????????lv?=?nodes[i]
????????????rv?=?nodes[i?+?1]
????????????i?+=?2
????????????#?對于給的的 level x，從左到右依次對應(yīng) level x + 1 的節(jié)點(diǎn)
????????????#?node?是?level?x?的節(jié)點(diǎn)，l?和?r?則是?level?x?+?1?的節(jié)點(diǎn)
????????????if?lv?!=?'#':
????????????????l?=?TreeNode(lv)
????????????????node.left?=?l
????????????????queue.append(l)
????????????if?rv?!=?'#':
????????????????r?=?TreeNode(rv)
????????????????node.right?=?r
????????????????queue.append(r)
????????return?root
「復(fù)雜度分析」
時(shí)間復(fù)雜度：每個(gè)節(jié)點(diǎn)都會被處理一次，因此時(shí)間復(fù)雜度為?，其中??為節(jié)點(diǎn)的總數(shù)。 空間復(fù)雜度：，其中??為節(jié)點(diǎn)的總數(shù)。
總結(jié)
除了這種方法還有很多方案， 比如括號表示法。關(guān)于這個(gè)可以參考力扣606. 根據(jù)二叉樹創(chuàng)建字符串，這里就不再贅述了。
本文從 BFS 和 DFS 角度來思考如何序列化和反序列化一棵樹。如果用 BFS 來序列化，那么相應(yīng)地也需要 BFS 來反序列化。如果用 DFS 來序列化，那么就需要用 DFS 來反序列化。
我們從馬后炮的角度來說，實(shí)際上對于序列化來說，BFS 和 DFS 都比較常規(guī)。對于反序列化，大家可以像我這樣舉個(gè)例子，畫一個(gè)圖?？梢韵仍诩埳?，電腦上，如果你熟悉了之后，也可以畫在腦子里。
（Like This）
來個(gè)直擊靈魂的三連吧！