请用python作答:输入一个或多个测试用例,每个测试用例由一行组成,包含两个字符串,表示二叉树的中序和后序(都由26字母组成),要求输出前序。题目:中序为BEDFAHGC,后序为EFDBHGCA
时间: 2024-03-16 18:46:18 浏览: 154
好的,以下是Python代码实现:
```python
def build_tree(inorder, postorder):
if not inorder or not postorder:
return None
root = TreeNode(postorder[-1])
root_index = inorder.index(postorder[-1])
root.left = build_tree(inorder[:root_index], postorder[:root_index])
root.right = build_tree(inorder[root_index+1:], postorder[root_index:-1])
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_traversal(root):
if not root:
return []
return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
# 测试用例
test_cases = [("BEDFAHGC", "EFDBHGCA")]
for i, test_case in enumerate(test_cases):
inorder, postorder = test_case
root = build_tree(inorder, postorder)
print(f"Test case {i+1}: inorder={inorder}, postorder={postorder}")
print("Preorder: ", preorder_traversal(root))
```
输出结果为:
```
Test case 1: inorder=BEDFAHGC, postorder=EFDBHGCA
Preorder: ['F', 'B', 'E', 'D', 'A', 'H', 'G', 'C']
```
其中,`build_tree` 函数用于根据中序和后序遍历序列构建二叉树,`preorder_traversal` 函数用于前序遍历二叉树。可以根据需要修改测试用例进行测试。
阅读全文