通过键盘输入二叉树先序序列和中序序列,将遍历结果后序序列输出
时间: 2023-04-29 22:00:10 浏览: 122
这道题需要用到二叉树的遍历知识,先序遍历的顺序是根节点-左子树-右子树,中序遍历的顺序是左子树-根节点-右子树,后序遍历的顺序是左子树-右子树-根节点。
我们可以通过先序序列找到根节点,然后在中序序列中找到根节点的位置,这样就可以确定左子树和右子树的范围。然后分别对左子树和右子树进行递归,直到叶子节点为止。
最后将左子树的后序序列和右子树的后序序列拼接起来,再加上根节点,就是整个二叉树的后序序列了。
具体实现可以参考下面的代码:
```python
def build_tree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[]
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = build_tree(preorder[1:idx+1], inorder[:idx])
root.right = build_tree(preorder[idx+1:], inorder[idx+1:])
return root
def postorder_traversal(root):
if not root:
return []
res = []
res.extend(postorder_traversal(root.left))
res.extend(postorder_traversal(root.right))
res.append(root.val)
return res
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = build_tree(preorder, inorder)
postorder = postorder_traversal(root)
print(postorder) # [4, 5, 2, 6, 7, 3, 1]
```
这里假设二叉树的节点类为`TreeNode`,包含`val`、`left`和`right`三个属性。`build_tree`函数用于构建二叉树,`postorder_traversal`函数用于遍历二叉树并返回后序序列。最后我们可以将先序序列和中序序列作为参数传入`build_tree`函数,得到二叉树的根节点,再将根节点作为参数传入`postorder_traversal`函数,得到后序序列。
阅读全文