发表于 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))

• LC 题目链接