给定一棵二叉树的先序遍历序列和中序遍历序列,求解: 1、这棵树的后序遍历序列; 2、从这棵树的右侧观察该树,从根节点到叶子节点,依次输出能被观测到的节点序列。
时间: 2023-12-23 09:04:56 浏览: 68
对所建立的二叉树分别进行先序、中序和后序遍历,并输出结果。
4星 · 用户满意度95%
1. 首先根据先序遍历序列确定根节点,然后在中序遍历序列中找到根节点的位置,可以将中序遍历序列分成左右两个子序列,左子序列为根节点的左子树,右子序列为根节点的右子树。
2. 对左子树和右子树分别进行递归处理,得到左子树的后序遍历序列和右子树的后序遍历序列。
3. 最后将根节点加入到左右子树的后序遍历序列的末尾,就得到了整棵树的后序遍历序列。
下面是具体的代码实现:
```python
def build_tree(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
inorder_index = inorder.index(root_val)
left_inorder = inorder[:inorder_index]
right_inorder = inorder[inorder_index+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
root.left = build_tree(left_preorder, left_inorder)
root.right = build_tree(right_preorder, right_inorder)
return root
def postorder_traversal(root):
if not root:
return []
left_postorder = postorder_traversal(root.left)
right_postorder = postorder_traversal(root.right)
return left_postorder + right_postorder + [root.val]
def right_side_view(root):
if not root:
return []
right_view = []
queue = [root]
while queue:
size = len(queue)
for i in range(size):
node = queue.pop(0)
if i == size-1:
right_view.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return right_view
```
其中,在代码中,`TreeNode` 表示二叉树节点的类,包含 `val`、`left` 和 `right` 三个成员变量。`build_tree` 函数用于根据先序遍历序列和中序遍历序列构建二叉树;`postorder_traversal` 函数用于计算二叉树的后序遍历序列;`right_side_view` 函数用于计算从右侧观察该树能够看到的节点序列。
阅读全文