日野弥生：勉強しよう
LeetCode 106 - 从中序与后序遍历序列构造二叉树
发表于2025年02月20日
本题的关键是要想明白：
- 后序遍历的最后一个结点是根节点；
- 根节点在中序遍历中可以把中序遍历列表分为左子树和右子树
- 且根节点的相对位置可以确定后序遍历列表中的左右子树，因为后序遍历的顺序一定是左子树-右子树-根。所以相对位置可以确定出递归过程传递给递归函数的子列表。
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# 列表均不能为空
if not inorder or not postorder:
return None
# 先处理根节点
root = TreeNode(postorder[-1], None, None)
# 找到根结点的相对位置
rootIndex = inorder.index(root.val)
# 中序和后序中存储的左子树的长度一定是一样的
root.left = self.buildTree(inorder[:rootIndex], postorder[:rootIndex])
# python切片是前闭后开的
root.right = self.buildTree(inorder[rootIndex + 1:],postorder[rootIndex:-1])
return root本题的list的index()函数效率不高，可以考虑用基于哈希技术的字典代替。