算法：序列化二叉树

分手后的思念是犯贱 2024-04-06 14:04 71阅读 0赞

![606888b6d3f29753ba138d28f2825f7f.jpeg][]

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

## 示例 ##

![e373e5d59db9d1f2215c1a969963f11a.jpeg][]

*  输入：root = \[1,2,3,null,null,4,5\]
 *  输出：\[1,2,3,null,null,4,5\]

## 方法：层序遍历BFS ##

**序列化：**![15b02e5ed5bf42c9b1a27a2fc905732d.png][]

借助队列，对二叉树进行层序遍历，而且为了表示二叉树的完整性，我们也会把 null 节点也记录下来。

**代码如下：**

![d2734cc94fa58e6fe1e775387e243dac.jpeg][]

## 复杂度分析 ##

*  时间复杂度：O(N)，N 为二叉树的节点数。
 *  空间复杂度：O(N) 。

**反序列化：**

序列化后的字符串为“\[1,2,3,null,null,4,5,null,null,null,null\]”，归纳整理为下表：

<table> 
 <tbody> 
 <tr> 
 <td> node.val </td> 
 <td> node的索引 </td> 
 <td> left的索引 </td> 
 <td> right的索引 </td> 
 </tr> 
 <tr> 
 <td> 1 </td> 
 <td> 0 </td> 
 <td> 1 </td> 
 <td> 2 </td> 
 </tr> 
 <tr> 
 <td> 2 </td> 
 <td> 1 </td> 
 <td> 3 </td> 
 <td> 4 </td> 
 </tr> 
 <tr> 
 <td> 3 </td> 
 <td> 2 </td> 
 <td> 5 </td> 
 <td> 6 </td> 
 </tr> 
 <tr> 
 <td> 4 </td> 
 <td> 5 </td> 
 <td> 7 </td> 
 <td> 8 </td> 
 </tr> 
 <tr> 
 <td> 5 </td> 
 <td> 6 </td> 
 <td> 9 </td> 
 <td> 10 </td> 
 </tr> 
 <tr> 
 <td> …… </td> 
 <td> …… </td> 
 <td> …… </td> 
 <td> …… </td> 
 </tr> 
 <tr> 
 <td> ≠ null </td> 
 <td> n </td> 
 <td> 2(n - m) + 1 </td> 
 <td> 2(n - m) + 2 </td> 
 </tr> 
 <tr> 
 <td> = null </td> 
 <td> n </td> 
 <td> 无 </td> 
 <td> 无 </td> 
 </tr> 
 </tbody> 
</table>

基于我们分析的规律，利用队列按层构建二叉树，在这里我们需要一个指针来指向节点的左/右子节点，每构建一个节点的左/右子节点，指针就向右移动 1 位。

**代码如下：**

![20d2f21bc337246af2cbcbec3c5ad6f2.jpeg][]

## 复杂度分析 ##

*  时间复杂度：O(N) ，N 为二叉树的节点数。
 *  空间复杂度： O(N) 。

## END ##

勤奋是成功之母，懒惰乃万恶之源，赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。

![4fc10a8d54134e87898afad9c970d4f2.png][]

[606888b6d3f29753ba138d28f2825f7f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/d26d46733fe0442fa20185397671b552.jpeg
[e373e5d59db9d1f2215c1a969963f11a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/2de9613756704f0e8b253228c7a8d028.jpeg
[15b02e5ed5bf42c9b1a27a2fc905732d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/3c326158f6814712a81079881c40f657.png
[d2734cc94fa58e6fe1e775387e243dac.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/7979b475a8044c88b8196705c1af3f33.jpeg
[20d2f21bc337246af2cbcbec3c5ad6f2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/780f369eef0d4d938b5966abd6456994.jpeg
[4fc10a8d54134e87898afad9c970d4f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/55217e1405de41bfae63cda3812a0433.png