已知二叉树的层次遍历序列和中序遍历序列,输出先序遍历序列和后序遍历序列
时间: 2023-09-08 09:08:24 浏览: 114
可以通过递归的方式来解决该问题。
先考虑如何构造二叉树,由于已知中序遍历序列,可以找到根节点,再根据根节点在层次遍历序列中的位置,就可以确定左右子树的层次遍历序列。接着对左右子树进行递归构造即可。
以下是具体实现过程:
```python
def build_tree(level_order, in_order):
if not level_order or not in_order:
return None
root_val = level_order[0]
root = TreeNode(root_val)
root_idx = in_order.index(root_val)
root.left = build_tree(level_order[1:root_idx+1], in_order[:root_idx])
root.right = build_tree(level_order[root_idx+1:], in_order[root_idx+1:])
return root
```
接着使用先序遍历和后序遍历的递归方式输出即可。
```python
def pre_order(root):
if not root:
return []
return [root.val] + pre_order(root.left) + pre_order(root.right)
def post_order(root):
if not root:
return []
return post_order(root.left) + post_order(root.right) + [root.val]
```
完整代码如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def build_tree(level_order, in_order):
if not level_order or not in_order:
return None
root_val = level_order[0]
root = TreeNode(root_val)
root_idx = in_order.index(root_val)
root.left = build_tree(level_order[1:root_idx+1], in_order[:root_idx])
root.right = build_tree(level_order[root_idx+1:], in_order[root_idx+1:])
return root
def pre_order(root):
if not root:
return []
return [root.val] + pre_order(root.left) + pre_order(root.right)
def post_order(root):
if not root:
return []
return post_order(root.left) + post_order(root.right) + [root.val]
level_order = [1, 2, 3, 4, 5, 6, 7]
in_order = [4, 2, 5, 1, 6, 3, 7]
root = build_tree(level_order, in_order)
print("先序遍历序列:", pre_order(root))
print("后序遍历序列:", post_order(root))
```
输出结果为:
```
先序遍历序列: [1, 2, 4, 5, 3, 6, 7]
后序遍历序列: [4, 5, 2, 6, 7, 3, 1]
```
阅读全文