JZX轻语：简
LeetCode 889- 根据前序和后序遍历构造二叉树
发表于2024年05月21日
类似于根据前序+中序遍历构造二叉树，不同之处在于仅根据前序和后序则不能构建一棵唯一的二叉树，即如果只有一个孩子的情况下，仅根据前序和后序遍历是无法得知其为左孩子还是右孩子。在每次递归下，如果当前子数组的长度为1，则此时子树仅只有一个节点，直接返回该节点即可；否则，该子树的根的值为前序遍历子数组的第一个元素，亦是后序遍历子数组的最后一个元素；而其第一个孩子(左孩子)的值为前序遍历子数组的第2个元素，而最后一个孩子(不一定是右孩子，可能还是左孩子)的值为后序遍历子数组的倒数第2个元素。如果第一个孩子的值等于最后一个孩子的值，则说明该节点仅有一个孩子。否则，根据上述信息，进一步切分成两个子数组继续递归下去。
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def build(pre_left: int, post_left: int, arr_size: int) -> Optional[TreeNode]:
root = TreeNode(preorder[pre_left])
if arr_size == 1:
return root
lc_val = preorder[pre_left + 1]
rc_val = postorder[post_left + arr_size - 2]
if lc_val == rc_val: # 如果相等, 说明只有一个孩子节点而已(没有中序遍历无法严格重构一棵树)
# 此时全部作为左孩子
root.left = build(pre_left + 1, post_left, arr_size - 1)
else:
# 进一步切成两个子数组递归重建左子树和右子树
# 找到右孩子在前序遍历的位置
rc_pos_in_pre = preorder.index(rc_val)
# 确定左子树对应的子数组的长度
lc_arr_size = rc_pos_in_pre - pre_left - 1
# 递归构建
root.left = build(pre_left + 1, post_left, lc_arr_size)
root.right = build(pre_left + 1 + lc_arr_size, post_left + lc_arr_size, arr_size - 1 - lc_arr_size)
return root
if len(preorder) == 0:
return None
return build(0, 0, len(preorder))