代码收藏家 PTA天梯赛Python专题：树的遍历详解
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
代码实现：
# 定义TreeNode 二叉树类，__init__ 方法初始化val的值
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 定义重建二叉树的函数
def build_tree(postorder, inorder):
if not postorder or not inorder:
return None
# 后序遍历的最后一个节点是根节点
root_val = postorder[-1]
root = TreeNode(root_val)
# 在中序遍历中找到根节点的位置
root_index = inorder.index(root_val)
# 左子树的中序遍历和后序遍历
left_inorder = inorder[:root_index]
left_postorder = postorder[:root_index]
# 右子树的中序遍历和后序遍历
right_inorder = inorder[root_index + 1:]
right_postorder = postorder[root_index:-1]
# 递归构建左子树和右子树
root.left = build_tree(left_postorder, left_inorder)
root.right = build_tree(right_postorder, right_inorder)
return root
# 层序遍历，广度优先搜索（BFS）
def level_order_traversal(root):
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 输入处理
n = int(input().strip())
postorder = list(map(int, input().strip().split()))
inorder = list(map(int, input().strip().split()))
# 重建二叉树
root = build_tree(postorder, inorder)
# 层序遍历
result = level_order_traversal(root)
# 输出结果
print(" ".join(map(str, result)))相关知识：
一、类的构造方法
def __init__(self, x)，当创建类的实例时，__init__ 方法会被自动调用
二、根据后序中序得到原二叉树
-
确定根节点：后序遍历的最后一个元素是
4，所以根节点的值是4。 -
在中序遍历中找到根节点的位置：在中序遍历
[1, 2, 3, 4, 5, 6, 7]中，4的位置是索引3。 -
将中序遍历分为左子树和右子树：
-
左子树的中序遍历：
[1, 2, 3] -
右子树的中序遍历：
[5, 6, 7] -
将后序遍历分为左子树和右子树：
-
左子树的后序遍历：
[2, 3, 1]（前3个元素） -
右子树的后序遍历：
[5, 7, 6]（从第4个元素到倒数第二个元素） -
递归地对左子树和右子树进行上述步骤：
-
对左子树（后序：
[2, 3, 1]，中序：[1, 2, 3]）： -
根节点是
1 -
在中序遍历中，
1的位置是索引0 -
左子树的中序遍历：
[]（空） -
右子树的中序遍历：
[2, 3] -
左子树的后序遍历：
[]（空） -
右子树的后序遍历：
[2, 3] -
递归地对右子树（后序：
[2, 3]，中序：[2, 3]）： -
根节点是
3 -
在中序遍历中，
3的位置是索引1 -
左子树的中序遍历：
[2] -
右子树的中序遍历：
[]（空） -
左子树的后序遍历：
[2] -
右子树的后序遍历：
[]（空） -
递归地对左子树（后序：
[2]，中序：[2]）： -
根节点是
2 -
在中序遍历中，
2的位置是索引0 -
左子树和右子树都是空
-
对右子树（后序：
[5, 7, 6]，中序：[5, 6, 7]）： -
根节点是
6 -
在中序遍历中，
6的位置是索引1 -
左子树的中序遍历：
[5] -
右子树的中序遍历：
[7] -
左子树的后序遍历：
[5] -
右子树的后序遍历：
[7] -
递归地对左子树（后序：
[5]，中序：[5]）： -
根节点是
5 -
在中序遍历中，
5的位置是索引0 -
左子树和右子树都是空
-
递归地对右子树（后序：
[7]，中序：[7]）： -
根节点是
7 -
在中序遍历中，
7的位置是索引0 -
左子树和右子树都是空
最终得到原来的二叉树如下
4
/ \
1 6
\ / \
3 5 7
/
2三、层序遍历，广度优先搜索（BFS）
初始状态
root = TreeNode(4)，根节点的值为 4。
result = []，结果列表为空。
queue = [root]，队列中只有根节点。
第一次循环
-
从队列中取出节点：
-
node = queue.pop(0)，取出根节点4。 -
将节点值加入结果列表：
-
result.append(node.val)，result = [4]。 -
将子节点加入队列：
-
queue.append(node.left)，加入左子节点1。 -
queue.append(node.right)，加入右子节点6。 -
队列状态：
queue = [1, 6]。
第二次循环
-
从队列中取出节点：
-
node = queue.pop(0)，取出节点1。 -
将节点值加入结果列表：
-
result.append(node.val)，result = [4, 1]。 -
将子节点加入队列：
-
queue.append(node.left)，左子节点为空，不加入。 -
queue.append(node.right)，加入右子节点3。 -
队列状态：
queue = [6, 3]。
第三次循环
-
从队列中取出节点：
-
node = queue.pop(0)，取出节点6。 -
将节点值加入结果列表：
-
result.append(node.val)，result = [4, 1, 6]。 -
将子节点加入队列：
-
queue.append(node.left)，加入左子节点5。 -
queue.append(node.right)，加入右子节点7。 -
队列状态：
queue = [3, 5, 7]。
第四次循环
-
从队列中取出节点：
-
node = queue.pop(0)，取出节点3。 -
将节点值加入结果列表：
-
result.append(node.val)，result = [4, 1, 6, 3]。 -
将子节点加入队列：
-
queue.append(node.left)，加入左子节点2。 -
queue.append(node.right)，右子节点为空，不加入。 -
队列状态：
queue = [5, 7, 2]。
第五次循环
-
从队列中取出节点：
-
node = queue.pop(0)，取出节点5。 -
将节点值加入结果列表：
-
result.append(node.val)，result = [4, 1, 6, 3, 5]。 -
将子节点加入队列：
-
左右子节点都为空，不加入。
-
队列状态：
queue = [7, 2]。
第六次循环
-
从队列中取出节点：
-
node = queue.pop(0)，取出节点7。 -
将节点值加入结果列表：
-
result.append(node.val)，result = [4, 1, 6, 3, 5, 7]。 -
将子节点加入队列：
-
左右子节点都为空，不加入。
-
队列状态：
queue = [2]。
第七次循环
-
从队列中取出节点：
-
node = queue.pop(0)，取出节点2。 -
将节点值加入结果列表：
-
result.append(node.val)，result = [4, 1, 6, 3, 5, 7, 2]。 -
将子节点加入队列：
-
左右子节点都为空，不加入。
-
队列状态：
queue = []。
循环结束
队列为空，循环结束。
返回结果列表：result = [4, 1, 6, 3, 5, 7, 2]。
作者：胡同Alley
