日野弥生：勉強しよう
LeetCode 105 - 从前序与中序遍历序列构造二叉树
发表于2025年02月21日
与上一题类似，先找出先序遍历中的第一个结点，即根节点。在利用根节点在中序遍历的相对位置确定左右子树的列表。从而递归传递下去。
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
rootVal = preorder[0]
root = TreeNode(rootVal)
rootIndex = inorder.index(rootVal)
# 需要注意前闭后开
root.left = self.buildTree(preorder[1:rootIndex + 1], inorder[:rootIndex])
root.right = self.buildTree(preorder[rootIndex + 1:], inorder[rootIndex + 1:])
return root本题的list的index()函数效率不高，可以考虑用基于哈希技术的字典代替。