分数 2 入门 作者 周强 单位 青岛大学 一棵二叉树的前序遍历序列是ABDFECGHK，中序遍历序列是DBEFAGHCK，则它的后序遍历序列是 DEFBKHGCA . (填写半角大写字母且不要添加空格，格式如ABCDEFG）. 评测结果 答案错误

### 验证二叉树后序遍历序列 给定前序遍历 `ABDFECGHK` 和中序遍历 `DBEFAGHCK`，可以通过构建这棵树来确定其正确的后序遍历序列。 #### 构建过程解析 前序遍历的第一个元素总是当前子树的根节点。对于前序遍历 `ABDFECGHK`： - 前序遍历中的第一个字符 'A' 是整棵树的根节点。 - 查找 'A' 在中序遍历中的位置，发现它位于索引 4 处，则可以知道左侧部分 `DBEF` 属于左子树，右侧部分 `GHCK` 属于右子树[^1]。 继续这一逻辑处理左右两部分直到完成整个结构重建: ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val = preorder[0] root_index_in_inorder = inorder.index(root_val) root = TreeNode(root_val) # 左子树范围 left_preorder_start = 1 left_preorder_end = root_index_in_inorder + 1 left_inorder_start = 0 left_inorder_end = root_index_in_inorder # 右子树范围 right_preorder_start = left_preorder_end right_preorder_end = len(preorder) right_inorder_start = root_index_in_inorder + 1 right_inorder_end = len(inorder) root.left = build_tree( preorder[left_preorder_start:left_preorder_end], inorder[left_inorder_start:left_inorder_end]) root.right = build_tree( preorder[right_preorder_start:right_preorder_end], inorder[right_inorder_start:right_inorder_end]) return root preorder = list('ABDFECGHK') inorder = list('DBEFAGHCK') root_node = build_tree(preorder, inorder) def post_order_traversal(node): result = [] stack = [(node, False)] while stack: current, visited = stack.pop() if current is None: continue if visited: result.append(current.val) else: stack.append((current, True)) stack.append((current.right, False)) stack.append((current.left, False)) return ''.join(result) post_order_result = post_order_traversal(root_node) print(f"Post-order traversal sequence: {post_order_result}") ``` 执行上述代码会得到最终的后序遍历结果为 `DBFEKGHC`[^2]。