难度: Medium
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。
示例 1：
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1] 输出：[1,2,3,4,5,6,7]
示例 2:
输入: preorder = [1], postorder = [1] 输出: [1]
提示：
1 <= preorder.length <= 301 <= preorder[i] <= preorder.lengthpreorder 中所有值都 不同postorder.length == preorder.length1 <= postorder[i] <= postorder.lengthpostorder 中所有值都 不同preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历运行时间: 20 ms
内存: 16.2 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def myTree(preorder_left:int, preorder_right: int, postorder_left: int, postorder_right: int):
# 终止条件
if preorder_left > preorder_right:
return None
preorder_root = preorder_left
# 创建根结点
root = TreeNode(preorder[preorder_root])
# 获取左子树大小
# preorder_index[postorder[-2]]
if preorder_left + 1 > preorder_right:
return root
size_left_subtree = postorder_index[preorder[preorder_left + 1]] - postorder_left + 1
root.left = myTree(preorder_left + 1, preorder_left + size_left_subtree, postorder_left, postorder_left + size_left_subtree - 1)
root.right = myTree(preorder_left + size_left_subtree + 1, preorder_right, postorder_left + size_left_subtree, postorder_right - 1)
return root
n = len(postorder)
postorder_index = {element: i for i, element in enumerate(postorder)}
# preorder_index = {element: i for i, element in enumerate(preorder)}
return myTree(0, n - 1, 0, n - 1)
这个题解使用递归的方法来构建二叉树。主要思路是根据前序遍历和后序遍历的特点，找到根节点和左右子树的范围，递归地构建左右子树。具体来说： 1. 前序遍历的第一个元素是根节点 2. 在后序遍历中找到前序遍历第二个元素的位置，可以得到左子树的大小 3. 根据左子树大小，可以确定前序遍历和后序遍历中左右子树的范围 4. 递归地构建左子树和右子树 5. 返回根节点
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def myTree(preorder_left:int, preorder_right: int, postorder_left: int, postorder_right: int):
# 终止条件：前序遍历的左指针大于右指针
if preorder_left > preorder_right:
return None
# 获取前序遍历的根节点下标
preorder_root = preorder_left
# 创建根结点
root = TreeNode(preorder[preorder_root])
# 如果前序遍历的左指针加1大于右指针，说明已经没有子节点了，直接返回当前根节点
if preorder_left + 1 > preorder_right:
return root
# 计算左子树的大小：
# 在后序遍历中找到前序遍历第二个元素的下标，它与后序遍历左指针的差加1就是左子树大小
size_left_subtree = postorder_index[preorder[preorder_left + 1]] - postorder_left + 1
# 递归构建左子树
root.left = myTree(preorder_left + 1, preorder_left + size_left_subtree, postorder_left, postorder_left + size_left_subtree - 1)
# 递归构建右子树
root.right = myTree(preorder_left + size_left_subtree + 1, preorder_right, postorder_left + size_left_subtree, postorder_right - 1)
return root
# 获取二叉树节点数
n = len(postorder)
# 用哈希表存储后序遍历中每个元素的下标，便于查找
postorder_index = {element: i for i, element in enumerate(postorder)}
# 调用递归函数，传入前序遍历和后序遍历的左右指针
return myTree(0, n - 1, 0, n - 1)
在构建二叉树的过程中，当前序遍历的左指针大于右指针时，这表示当前递归处理的子数组不包含任何元素，即当前递归范围内没有节点可以构建，故应终止递归。此条件是递归终止的基本逻辑，确保不会对空数组进行无效的操作或尝试访问不存在的数组元素。
是的，前序和后序遍历序列可能对应多个不同的二叉树结构，特别是在二叉树的结构不是完全确定的情况下。例如，对于前序遍历序列 [2, 1] 和后序遍历序列 [1, 2]，可以构建两种不同的二叉树结构：一种是根节点为2，左子树为1，右子树为空；另一种是根节点为2，左子树为空，右子树为1。这两种结构的前序和后序遍历结果相同，但二叉树结构不同。
为了正确无误地分割左右子树，解题策略中利用了前序和后序遍历的特点。在前序遍历中，根节点后的第一个元素代表左子树的根节点；在后序遍历中，此左子树的根节点的位置可以标识出整个左子树的范围。通过在后序遍历中找到这个左子树根节点的位置，我们可以计算出左子树的大小，然后根据这个大小在前序和后序遍历中分别划分出左右子树的元素范围。这样每次递归都能准确地处理相应的子树。
哈希表`postorder_index`存储了后序遍历中每个元素的索引位置，这样在需要找到任何元素在后序遍历中的位置时，可以直接通过哈希表以常数时间O(1)完成查找，而不需要遍历整个后序遍历数组来搜索元素，从而避免了O(n)的时间复杂度。在递归构建二叉树时，这种快速查找显著提高了效率，特别是在频繁地确定子树范围时，哈希表的作用尤为重要。