[面试][算法]基于二叉树的先序中序后序遍历序列重建二叉树

基于任意两种遍历序列都可以重建二叉树吗？

答案是不能。只有“先+中”、”后+中“才可以重建，而”先+后“是无法重建的。

这是因为： 先序与后序的最大优势是可以确认根节点的所在(首部或尾部)，然后基于中序得到左子树和右子树的尺寸，进而递归分治。但”先+后“拥有类似的知识，即可以知道根节点在何处但无法划分左右子树，因此在线性复杂度下不可解。

重建二叉树和二叉树的反序列化有何区别？

二叉树的序列化对”空节点“进行了标记，而简单的遍历序列由于缺失了空节点信息，因此单序列无法重建二叉树，必须要双序列配合才可以。

从《[算法][面试]二叉树的序列化与反序列化(bfs|先序、后序)》我们已知其仅可在先序、后序遍历序列化的情况下进行反序列化。

代码：

def rebuild_pre_in(preorder: List[int], inorder: List[int]) -> TreeNode or None: # 从前序和中序复原二叉树 if len(preorder) == 0: return None root = TreeNode(preorder[0]) root_in_id = inorder.index(preorder[0]) # 在中序中定位根节点的位置 root.left = rebuild_pre_in(preorder[1:1 + root_in_id], inorder[:root_in_id]) root.right = rebuild_pre_in(preorder[1 + root_in_id:], inorder[root_in_id + 1:]) return root def rebuild_pre_pos(preorder: List[int], posorder: List[int]) -> TreeNode or None: # 从前序和后序复原二叉树是不可能的 pass def rebuild_in_pos(inorder: List[int], posorder: List[int]) -> TreeNode or None: # 从中序和后序复原二叉树 if len(posorder) == 0: return None root = TreeNode(posorder[-1]) root_in_id = inorder.index(posorder[-1]) # 在中序中定位根节点的位置 root.left = rebuild_in_pos(inorder[:root_in_id], posorder[:root_in_id]) root.right = rebuild_in_pos(inorder[root_in_id + 1:], posorder[root_in_id:-1]) return root