python3代码,题目是这样的: 请根据二叉树的前序遍历,中序遍历恢复二叉树,并打印出二叉树的右视图
时间: 2023-02-10 09:11:27 浏览: 56
确定每个节点的左右子节点需要使用前序遍历和中序遍历两个序列。前序遍历的第一个节点一定是根节点,在中序遍历中找到根节点,根节点左边的节点都是左子树,右边的节点都是右子树。然后递归构建左子树和右子树。
例如,对于以下二叉树:
```
1
/ \
2 3
/ \ \
4 5 6
```
前序遍历为 `[1, 2, 4, 5, 3, 6]`,中序遍历为 `[4, 2, 5, 1, 3, 6]`。
那么,可以使用以下 Python 代码恢复二叉树:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
root_index = inorder.index(preorder[0])
root.left = build_tree(preorder[1:root_index+1], inorder[:root_index])
root.right = build_tree(preorder[root_index+1:], inorder[root_index+1:])
return root
def print_right_view(root):
if not root:
return
queue = [root]
while queue:
level_size = len(queue)
for i in range(level_size):
current_node = queue.pop(0)
if i == level_size - 1:
print(current_node.val)
if current_node.left:
queue.append(current_node.left)
if current_node.right:
queue.append(current_node.right)
preorder = [1, 2, 4, 5, 3, 6]
inorder = [4, 2, 5, 1, 3, 6]
root = build_tree(preorder, inorder)
print_right_view(root)
```
输出结果为:
```
1
3
6
```
阅读全文