LeetCode 题解工作台
根据前序和后序遍历构造二叉树
给定两个整数数组， preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历， postorder 是同一棵树的后序遍历，重构并返回二叉树。 如果存在多个答案，您可以返回其中 任何 一个。 示例 1： 输入： preorder = [1,2,4,5…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
前序遍历的顺序是：根节点 -> 左子树 -> 右子树，后序遍历的顺序是：左子树 -> 右子树 -> 根节点。 因此，二叉树的根节点一定是前序遍历的第一个节点，也是后序遍历的最后一个节点。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定两个整数数组，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是同一棵二叉树的前序遍历和后序遍历
解题思路
方法一：递归
前序遍历的顺序是：根节点 -> 左子树 -> 右子树，后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
因此，二叉树的根节点一定是前序遍历的第一个节点，也是后序遍历的最后一个节点。
接下来，我们需要确定二叉树的左子树范围和右子树范围。
如果二叉树有左子树，那么左子树的根节点一定是前序遍历的第二个节点；如果二叉树没有左子树，那么前序遍历的第二个节点一定是右子树的根节点。由于这两种情况下，后序遍历的结果是一样的，因此，我们可以把前序遍历的第二个节点作为左子树的根节点，然后找到它在后序遍历中的位置，这样就确定了左子树的范围。
具体地，我们设计一个递归函数 ，其中 表示前序遍历的范围，而 表示后序遍历的范围。这个函数的功能是根据前序遍历 和后序遍历 构造出二叉树的根节点。那么答案就是 ，其中 是前序遍历的长度。
函数 的执行步骤如下：
- 如果 ，说明范围为空，直接返回空节点。
- 否则，我们构造一个新的节点 ，它的值为前序遍历中的第一个节点的值，也就是 。
- 如果 等于 ，说明 没有左子树也没有右子树，直接返回 。
- 否则，左子树的根节点的值为 ，我们在后序遍历中找到 的位置，记为 。那么左子树的节点个数 ，由此可知左子树在前序遍历中的范围是 ，后序遍历中的范围是 ，右子树在前序遍历中的范围是 ，后序遍历中的范围是 。
- 知道了左右子树的范围，我们就可以递归地重建左右子树，然后将左右子树的根节点分别作为 的左右子节点。最后返回 。
在函数 中，我们需要用到一个哈希表 ，它存储了后序遍历中每个节点的位置。在函数的开头，我们可以先计算出这个哈希表，这样就可以在 的时间内找到任意节点在后序遍历中的位置。
时间复杂度 ，空间复杂度 。其中 是节点数。
# 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 dfs(a: int, b: int, c: int, d: int) -> Optional[TreeNode]:
if a > b:
return None
root = TreeNode(preorder[a])
if a == b:
return root
i = pos[preorder[a + 1]]
m = i - c + 1
root.left = dfs(a + 1, a + m, c, i)
root.right = dfs(a + m + 1, b, i + 1, d - 1)
return root
pos = {x: i for i, x in enumerate(postorder)}
return dfs(0, len(preorder) - 1, 0, len(postorder) - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Ability to handle recursive problems efficiently.
- question_mark
Understanding of hash maps and their applications in tree construction.
- question_mark
Proficiency in managing multiple traversal patterns in binary trees.
常见陷阱
外企场景- error
Not correctly handling recursive base cases, leading to incorrect tree construction.
- error
Misunderstanding how to split the preorder and postorder arrays into subtrees.
- error
Inefficient lookup or missing hash map optimization for faster element positions.
进阶变体
外企场景- arrow_right_alt
Consider cases with trees containing only one node.
- arrow_right_alt
Explore variations with non-distinct values in the arrays.
- arrow_right_alt
Test the algorithm with the maximum allowed input size (30 nodes).