刷题笔记合集🔗

二叉树的广度优先遍历

问题描述

小毛有一棵二叉树，每个节点由一个大写字母标识（最多26个节点）。

现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出层序遍历的结果。层序遍历是指从树的顶层开始向下，每层中按照从左向右的顺序遍历节点。

输入格式

每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果。（每串只包含大写字母）

中间用单空格分隔。

输出格式

输出仅一行，表示层序遍历的结果，结尾换行。

样例输入

CBEFDA CBAEDF

样例输出

ABDCEF

数据范围

• 节点数
• 节点值仅为大写字母

题解

这道题目要求根据二叉树的后序遍历和中序遍历结果，输出层序遍历结果。

首先回顾一下三种常见的遍历方式：

• 前序遍历（根-左-右）
• 中序遍历（左-根-右）
• 后序遍历（左-右-根）

层序遍历则是按照树的层级，从上到下，从左到右依次访问每个节点。

解题思路是：根据后序遍历和中序遍历重建二叉树，然后进行层序遍历。

具体步骤如下：

1. 从后序遍历结果中确定根节点（后序遍历的最后一个元素）
2. 在中序遍历中找到根节点位置，根节点左边是左子树，右边是右子树
3. 根据左右子树的长度，将后序遍历结果也分成左右子树部分
4. 递归处理左右子树，重建整个二叉树
5. 使用队列实现层序遍历，从上到下、从左到右遍历节点

不过，我们可以用更巧妙的方法避免显式重建树结构。我们可以直接使用广度优先搜索（BFS）来实现层序遍历效果：

1. 从后序遍历找到根节点
2. 根据中序遍历将树分为左右子树
3. 将当前根节点加入结果
4. 将左右子树的后序和中序遍历结果作为新的任务加入队列
5. 从队列取出任务并重复上述步骤

时间复杂度分析：虽然看起来我们有嵌套循环，但每个节点只会被处理一次，所以时间复杂度为O(n)，其中n是节点数量。空间复杂度也是O(n)，用于存储队列和结果。

对于给定的数据范围（最多26个节点），这个算法是非常高效的。

参考代码

• Python

import sys
from collections import deque

input = lambda:sys.stdin.readline().strip()

# 读取输入
line = input()
post_order, in_order = line.split()

def bfs_traversal(post_order, in_order):
    """使用BFS实现层序遍历"""
    result = []  # 存储层序遍历结果
    queue = deque([(post_order, in_order)])  # 初始化队列
    
    while queue:
        post, inord = queue.popleft()
        
        # 如果子树为空，跳过
        if not post:
            continue
            
        # 根节点是后序遍历的最后一个元素
        root = post[-1]
        result.append(root)  # 添加到结果中
        
        # 找到根在中序遍历中的位置
        root_idx = inord.index(root)
        
        # 确定左右子树的大小
        left_size = root_idx
        
        # 分割左子树的后序和中序
        if left_size > 0:
            left_post = post[:left_size]
            left_in = inord[:root_idx]
            queue.append((left_post, left_in))
        
        # 分割右子树的后序和中序
        right_size = len(inord) - root_idx - 1
        if right_size > 0:
            right_post = post[left_size:-1]
            right_in = inord[root_idx+1:]
            queue.append((right_post, right_in))
    
    return ''.join(result)

print(bfs_traversal(post_order, in_order))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 使用广度优先搜索实现层序遍历
string bfsTraversal(string postOrder, string inOrder) {
    string result = "";
    queue<pair<string, string>> q;
    
    // 初始将整个树的