题目
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder 和 inorder 均 无重复 元素
- inorder 均出现在 preorder
- preorder 保证 为二叉树的前序遍历序列
- inorder 保证 为二叉树的中序遍历序列
我的代码（Python）
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def buildInner(preorder: List[int], rootIdx: int, inorder: List[int], startIdx: int, endIdx: int) -> Optional[TreeNode]:
print(f'rootIdx: {rootIdx}, startIdx: {startIdx}, endIdx: {endIdx}')
if startIdx >= endIdx or rootIdx >= len(preorder):
return None
result = TreeNode(preorder[rootIdx])
# if rootIdx == len(preorder) - 1:
# return result
try:
idx = inorder.index(preorder[rootIdx], startIdx, endIdx)
if startIdx < idx:
result.left = buildInner(preorder, rootIdx + 1, inorder, startIdx, idx)
result.right = buildInner(preorder, rootIdx + idx - startIdx + 1, inorder, idx + 1, endIdx)
return result
except ValueError:
return None
return buildInner(preorder, 0, inorder, 0, len(inorder))点评
递归创建，容易出错的地方在于计算左右结点时的索引边界及根结点索引。
官方多创建了一个哈希映射来存储索引，方便快速查找，这是个提升效率的好办法。
官方解法二用迭代，理解比较困难，也不容易想到（反正我没想到）……优势也比较微妙。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog