已知二叉树的先序遍历序列和中序遍历序列,输出其后序遍历序列和层次序遍历序列
时间: 2023-12-08 07:56:05 浏览: 103
二叉树的先序遍历,中序遍历,后序遍历,层级遍历
可以通过先序遍历序列和中序遍历序列重建二叉树,然后对重建后的二叉树进行后序遍历和层次遍历即可。
具体步骤如下:
1. 根据先序遍历序列确定根结点。
2. 在中序遍历序列中找到根结点所在位置,根结点左边的序列是左子树的中序遍历序列,右边的序列是右子树的中序遍历序列。
3. 通过左子树的中序遍历序列长度确定先序遍历序列中左子树的先序遍历序列,右子树的先序遍历序列为剩余部分。
4. 递归处理左子树和右子树,重建二叉树。
5. 对重建后的二叉树进行后序遍历和层次遍历。
下面是 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])
inorderIndex = inorder.index(preorder[0])
leftInorder = inorder[:inorderIndex]
rightInorder = inorder[inorderIndex+1:]
leftPreorder = preorder[1:len(leftInorder)+1]
rightPreorder = preorder[len(leftInorder)+1:]
root.left = buildTree(leftPreorder, leftInorder)
root.right = buildTree(rightPreorder, rightInorder)
return root
def postorderTraversal(root):
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
def levelOrder(root):
if not root:
return []
queue = [root]
res = []
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(postorderTraversal(root)) # 输出后序遍历序列 [4, 5, 2, 6, 7, 3, 1]
print(levelOrder(root)) # 输出层次遍历序列 [[1], [2, 3], [4, 5, 6, 7]]
```
阅读全文