前序遍历解法
-序列化:用栈实现树的前序遍历,先访问根节点(添加“val!”),然后将指针指向左节点,一直到左节点为空(添加“#!”),弹出一个节点,将指针指向右节点。如此反复直至栈为空且当前指针指向空。
-反序列化:还是仿照树的前序遍历,先添加根节点并入栈,指针指向根节点,若下一个字符不是空结点,则添加该节点为左节点并入栈,然后将指针指向该左节点,一直到左节点为空。此时我们需要找到节点中下一个不为空的值,以此来创建右节点并入栈,注意每有一个为空的值,便要从栈中弹出一个节点(表示当前节点的右节点为空,所以需要弹出当前节点的父节点)。如此反复直至栈为空。
注:python中字符串的split方法中,若字符串中最后一个字符为分割字符(此题中为“!”),则在生成的list会以空格符“ ”结尾,所以用nodes = nodes[:-1]来去掉末尾的空格。
class Solution: def Serialize(self, root): # write code here if not root: return "" res = "" stack = [] cur = root while stack or cur: if cur: stack.append(cur) res = res + str(cur.val) + "!" cur = cur.left else: res = res + "#" + "!" cur = stack.pop() cur = cur.right print res return res def Deserialize(self, s): # write code here if len(s) == 0: return None nodes = s.split("!") nodes = nodes[:-1] # Remove the space " " in the last position root = TreeNode(int(nodes[0])) sub = 1 stack = [] stack.append(root) cur = root while stack and sub < len(nodes): if nodes[sub] != "#": cur.left = TreeNode(int(nodes[sub])) cur = cur.left stack.append(cur) sub += 1 else: while sub < len(nodes) and nodes[sub] == "#": cur = stack.pop() sub += 1 if sub < len(nodes): cur.right = TreeNode(int(nodes[sub])) cur = cur.right stack.append(cur) sub += 1 return root
层序遍历解法
-序列化:树的层序遍历需要用队列实现,这里同样使用list实现,先将根节点入队,然后进入循环,出队一个节点(list中的第一个元素),访问该节点的值,若不为空则将其左右节点依次入队。如此反复直至队列为空。
-反序列化:同样用队列模仿层序遍历的过程,依次为每个节点建立左右节点即可。
class Solution: def Serialize(self, root): # write code here return self.BFS_tree(root) def Deserialize(self, s): # write code here if len(s) == 0: return None nodes = s.split("!") nodes = nodes[:-1] # Remove the space " " in the last position root = TreeNode(int(nodes[0])) Q = [] Q.append(root) sub = 1 while Q and sub < len(nodes): cur = Q[0] value = nodes[sub] sub += 1 if value == "#": cur.left = None else: cur.left = TreeNode(int(value)) Q.append(cur.left) value = nodes[sub] sub += 1 if value == "#": cur.right = None else: cur.right = TreeNode(int(value)) Q.append(cur.right) del Q[0] return root def BFS_tree(self, root): if not root: return [] Q = [] res = "" Q.append(root) while Q: cur = Q[0] if cur: res = res + str(cur.val) + "!" Q.append(cur.left) Q.append(cur.right) else: res = res + "#" + "!" del Q[0] return res