(1)由树的先序遍历序列和中序遍历序列创建一棵二叉树。 (2)输出二叉树的后序遍历序列
时间: 2023-11-23 17:54:32 浏览: 50
(1)由树的先序遍历序列和中序遍历序列创建一棵二叉树的步骤如下:
1. 根据先序遍历序列确定根节点,将中序遍历序列分为左子树和右子树两部分。
2. 递归处理左子树,得到左子树的根节点和左子树的先序遍历序列和中序遍历序列。
3. 递归处理右子树,得到右子树的根节点和右子树的先序遍历序列和中序遍历序列。
4. 将根节点与左右子树连接起来,得到一棵完整的二叉树。
(2)输出二叉树的后序遍历序列的步骤如下:
1. 先输出左子树的后序遍历序列。
2. 再输出右子树的后序遍历序列。
3. 最后输出根节点。
代码实现如下(Python):
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
def postorderTraversal(root):
if not root:
return []
res = []
res += postorderTraversal(root.left)
res += postorderTraversal(root.right)
res.append(root.val)
return res
n = int(input())
preorder = input()
inorder = input()
root = buildTree(preorder, inorder)
postorder = postorderTraversal(root)
print(' '.join(postorder))
```