已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，试画出该二叉树。

### 构造二叉树的过程 根据给定的中序遍历 `CBGEAFHD` 和后序遍历 `CGEBHFDA`，可以通过以下方法构造二叉树。 #### 1. 找到根节点 在后序遍历序列中，最后一个元素总是当前子树的根节点。因此，在后序遍历 `CGEBHFDA` 中，根节点为 `A`[^3]。 #### 2. 划分子树 通过中序遍历找到根节点的位置。在中序遍历 `CBGEAFHD` 中，根节点 `A` 的位置是第5位。由此可知： - 根节点左侧的部分 `CBGE` 是左子树的中序遍历； - 根节点右侧的部分 `FHD` 是右子树的中序遍历。 接着，从后序遍历中划分对应的子树部分。由于后序遍历的特点是从左至右依次处理左子树、右子树和根节点，所以： - 后序遍历中的前4个元素 `CGEB` 对应于左子树； - 接下来的3个元素 `HFD` 对应于右子树。 #### 3. 处理左子树 对于左子树，其对应的中序遍历为 `CBGE`，后序遍历为 `CGEB`。重复上述过程： - 在后序遍历 `CGEB` 中，根节点为 `B`。 - 在中序遍历 `CBGE` 中，`B` 的位置是第2位，因此： - 左子树为 `C`； - 右子树为 `GE`。 进一步分析： - 在后序遍历 `CGEB` 中，去掉根节点后的剩余部分为 `CGE`，其中 `C` 属于左子树，而 `GE` 属于右子树。 最终得出左子树结构如下： ```plaintext B / \ C G \ E ``` #### 4. 处理右子树 对于右子树，其对应的中序遍历为 `FHD`，后序遍历为 `HFD`。同样地： - 在后序遍历 `HFD` 中，根节点为 `D`。 - 在中序遍历 `FHD` 中，`D` 的位置是第3位，因此： - 左子树为 `FH`； - 右子树为空。 进一步分析： - 在后序遍历 `HFD` 中，去掉根节点后的剩余部分为 `HF`，其中 `H` 属于右子树，而 `F` 属于左子树。 最终得出右子树结构如下： ```plaintext D / F \ H ``` #### 5. 综合整棵树 综合以上两步的结果，完整的二叉树结构如下： ```plaintext A / \ B D / \ / C G F \ \ E H ``` --- ### 输出代码实现 以下是基于 Python 实现的构建二叉树函数： ```python class TreeNode: def __init__(self, val=0): self.val = val self.left = None self.right = None def build_tree(inorder, postorder): if not inorder or not postorder: return None root_val = postorder[-1] root_index_in_inorder = inorder.index(root_val) root = TreeNode(root_val) root.left = build_tree( inorder[:root_index_in_inorder], postorder[:root_index_in_inorder] ) root.right = build_tree( inorder[root_index_in_inorder + 1:], postorder[root_index_in_inorder:-1] ) return root # 测试数据 inorder = "CBGEAFHD" postorder = "CGEBHFDA" tree_root = build_tree(list(inorder), list(postorder)) print(tree_root.val) # 应输出 'A' ``` ---