[算法][面试]二叉树的序列化与反序列化(bfs|先序、后序)

前导知识

序列化与反序列化主要分为两个流派：dfs和bfs；由于二叉树的特殊性，dfs分为前序、中序、后序遍历，但只有前序和后序遍历才可以在线性复杂度下进行反序列化。

序列化

1. dfs

def serialize_dfs(root: TreeNode): # 直接利用递归，在通过三种方式内对二叉树进行序列化 res = {'pre': '', 'in': '', 'pos': ''} # 中序遍历无法反序列化，此处仅作补足 def dfs(node: TreeNode): if node is None: res['pre'] += "#," # 空节点标记为 '#' res['in'] += "#," res['pos'] += "#," else: res['pre'] += str(node.v) + "," # 使用 ',' 隔开每个节点 dfs(node.left) res['in'] += str(node.v) + "," dfs(node.right) res['pos'] += str(node.v) + "," dfs(root) return res

事实上，也可以利用非递归的方式进行dfs前、中、后序遍历，但都较难以归并到同一个函数下，故此处省略，若有兴趣可参考此出：【面试】算法：二叉树非递归形式的遍历及层级遍历。

2. bfs

def serialize_bfs(root): res = "" queue = [root] while queue: root = queue.pop() if root is None: res += "#," else: res += str(root.v) + "," queue.insert(0, root.left) queue.insert(0, root.right) return res

反序列化

1. bfs

实际上先序遍历和后序遍历的反序列化可以归于同一个框架下，但为了代码简洁可读我把它拆分成了两段代码，二者的本质是栈状态的初始化和扫描方向不同。

要想进行反序列化，需要有两个充要条件：1.知道根节点的位置；2.知道序列化的方法及何处为空节点。 显然，只有先序和后序遍历出来的序列才能满足条件1(先序根节点在序列的第一位、后序在末尾)；而中序显然就很难进行确认根节点在何处。

def deserialize_dfs_pre(string: str): # 先序反序列化 strings = string.split(',') index = -1 # 控制栈状态 def dfs(): nonlocal index # 在其他语言里，请把理解为 nonlocal => global 或 Class.static index += 1 if strings[index] == '#': return None node = TreeNode(int(strings[index])) node.left, node.right = dfs(), dfs() return node return dfs() def deserialize_dfs_pos(string: str): # 后序反序列化 strings = string.split(',') index = len(strings) - 1 # 由于split(',')，最后一位是''，因此从len(strings) - 1开始 def dfs(): nonlocal index index -= 1 if strings[index] == '#': return None node = TreeNode(int(strings[index])) node.right, node.left = dfs(), dfs() # 注意先右后左 return node return dfs()

2. bfs

def deserialize_bfs(string: str): # BFS反序列化 strings = string.split(',') if strings[0] == '#': # 处理空树的反序列化问题 return None root = TreeNode(int(strings[0])) is_left_child = True # 下一个节点是否为左节点 queue = [root] for i in range(1, len(strings) - 1): # 由于split(',')，最后一位是''，因此从len(strings) - 1 if strings[i] != '#': node = TreeNode(int(strings[i])) if is_left_child: queue[-1].left = node # 在其它语言里， queue[-1] => queue.peek() else: queue[-1].right = node queue.insert(0, node) if not is_left_child: # 当已经安排完右子树时，队列中第一个未安排的元素就出列 queue.pop() is_left_child = not is_left_child return root