序列化二叉树 java_剑指offer 序列化二叉树

刺骨的言语ヽ痛彻心扉 2022-10-23 11:29 286阅读 0赞

题目描述：

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

分析：

根据前序遍历的顺序来进行序列化，前序遍历是从根结点开始，在遍历二叉树碰到null指针时，就将其序列化为一个特殊字符，比如\#,另外，结点的数值之间用一个特殊字符(比如,)进行分隔。比如对于以下的树，序列化为字符串："1,2,4,\#,\#,\#,3,5,\#,\#,6,\#,\#"。

然后我们可以以"1,2,4,\#,\#,\#,3,5,\#,\#,6,\#,\#"为例来分析反序列化的过程，第一个读出1，这是根结点的值，然后读出2，这是根结点的左孩子，同样接下来的4是值为2的结点的左孩子结点；接下来读出两个“\#”，说明值为4的结点左右孩子都是null，这是一个叶结点。然后回到值为2的结点，重建它的右子树，由于下一个字符是“\#”，说明值为2的结点的右孩子结点为null，这个结点的左右子树都重建完毕，接下来再次回溯就到了根结点，所以，左子树重构完毕。

由于下一个数字是3，所以右子树的根结点值为3，左结点时一个值为5的叶结点(因为接下来的三个字符是5,\#,\#),同理右结点时一个值为6的结点。至此，重构完毕，反序列化完成。

序列化比较简单，就是一个前序遍历的过程，而反序列化也不难发现，实际就是一个递归解决每个子树的问题，详见以下代码实现。

python版本示例代码：

class TreeNode:

def \_\_\_init\_\_(self, x):

self.val = x

self.left = None

self.right = None

class Solution:

def Serialize(self, pRoot):

retlist = \[\]

def preOrder(pRoot):