二叉树遍历：由后序与中序推导层序结果（多语言实现）

讲解如何根据二叉树的后序遍历和中序遍历序列，推导出层序遍历结果。文章介绍了三种基本遍历方式的定义及区别，重点分析了利用后序和中序序列重建二叉树结构的逻辑。不同于传统的 DFS 递归建树再遍历，提供基于 BFS 队列优化的解法，直接按层序输出节点。提供了 JavaScript、Java、Python 和 C 四种语言的完整算法源码，涵盖输入处理、核心逻辑及链表/队列实现细节，适用于 ACM 模式下的编程练习。

涅槃凤凰发布于 2026/3/28更新于 2026/4/161 浏览

二叉树遍历：由后序与中序推导层序结果（多语言实现）

题目描述

有一棵二叉树，每个节点由一个大写字母标识 (最多 26 个节点）。现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出层序遍历的结果。

输入描述

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

输出描述

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

用例

输入

CBEFDA CBAEDF

输出

ABDCEF

说明

二叉树为：

A
/ \
B D
/ / \
C E F

题目解析

二叉树的三种遍历方式：

前序遍历：根节点 → 左子树 → 右子树
中序遍历：左子树 → 根节点 → 右子树
后序遍历：左子树 → 右子树 → 根节点

这三种遍历方式的命名依据是根节点的访问顺序：

"前"表示根节点最先访问
"中"表示根节点在中间访问
"后"表示根节点最后访问

无论哪种遍历方式，左右子树的访问顺序始终保持一致：先左后右。

掌握了二叉树遍历的基本原理后，我们可以进行实际案例分析。给定以下输入数据：

后序遍历序列：CBEFDA
中序遍历序列：CBAEDF

分析步骤如下：

根据后序遍历"左右根"的特性，序列最后一个元素 A 即为整棵树的根节点
在中序遍历"左根右"的序列中，根节点 A 将序列分为左右两部分：

左子树序列：CB
右子树序列：EDF

对左右子树重复上述过程：

在后序序列中找到子树根节点
在中序序列中划分新的左右子树

通过这种递归分解的方式，我们可以逐步构建出完整的二叉树结构。

当所找到的根节点左右子树仅含一个节点或无节点时，即可终止递归过程。递归完成后即可重建完整树形结构，按照层序遍历规则可直接得出结果：ABDCEF。

值得注意的是，本题看似需要通过深度优先搜索 (DFS) 构建树结构，实则可通过广度优先搜索 (BFS) 策略优化处理。采用 BFS 可直接实现层序遍历效果，无需先构建树结构再进行二次遍历。

BFS 层序遍历的具体实现逻辑如下：

根据后序遍历结果定位根节点 A
通过中序遍历结果确定根节点 A 的左右子树分布
由此可准确获取左右子树的规模信息

通过左右子树的长度，我们可以从后序遍历结果中划分出左子树和右子树部分，并确定它们各自的根节点（即对应部分的最后一个元素）。在遍历过程中，我们始终优先处理子树的根节点，然后再递归处理其左右子树。

JavaScript 算法源码

/* JavaScript Node ACM 模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
  input: process.,
  : process.,
});
rl.(,  {
   [post, mid] = line.();
  .((post, mid));
});

 () {
  
   queue = [];
  
   ans = [];
  (post, mid, queue, ans);
   (queue.) {
     [post, mid] = queue.();
    (post, mid, queue, ans);
  }
   ans.();
}


 () {
  
   rootEle = post.(-);
  
  ans.(rootEle);
  
   rootIdx = mid.(rootEle);
  
   leftLen = rootIdx;
  
   (leftLen > ) {
    
     leftPost = post.(, leftLen);
    
     leftMid = mid.(, rootIdx);
    
    queue.([leftPost, leftMid]);
  }
  
   (post. -  - leftLen > ) {
    
     rightPost = post.(leftLen, post. - );
    
     rightMid = mid.(rootIdx + );
    
    queue.([rightPost, rightMid]);
  }
}

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Keycode 信息

查找任何按下的键的javascript键代码、代码、位置和修饰符。在线工具，Keycode 信息在线工具，online

Escape 与 Native 编解码

JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。在线工具，Escape 与 Native 编解码在线工具，online

JavaScript / HTML 格式化

使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。在线工具，JavaScript / HTML 格式化在线工具，online

JavaScript 压缩与混淆

Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。在线工具，JavaScript 压缩与混淆在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String post = sc.next(); String mid = sc.next(); System.out.println(getResult(post, mid)); } /** * @param post 后序遍历结果 * @param mid 中序遍历结果 * @return 层序遍历结果 */ public static String getResult(String post, String mid) { // 广度优先搜索的执行队列，先加入左子树，再加入右子树 LinkedList<String[]> queue = new LinkedList<>(); // 层序遍历出来的元素存放在 ans 中 ArrayList<Character> ans = new ArrayList<>(); devideLR(post, mid, queue, ans); while (queue.size() > 0) { String[] tmp = queue.removeFirst(); devideLR(tmp[0], tmp[1], queue, ans); } StringBuilder sb = new StringBuilder(); for (Character c : ans) { sb.append(c); } return sb.toString(); } /** * 本方法用于从后序遍历、中序遍历序列中分离出：根，以及其左、右子树的后序、中序遍历序列 * * @param post 后序遍历结果 * @param mid 中序遍历结果 * @param queue BFS 的执行队列 * @param ans 题解 */ public static void devideLR( String post, String mid, LinkedList<String[]> queue, ArrayList<Character> ans) { // 后序遍历的最后一个元素就是根 char rootEle = post.charAt(post.length() - 1); // 将根加入题解 ans.add(rootEle); // 在中序遍历中找到根的位置 rootIdx，那么该位置左边就是左子树，右边就是右子树 int rootIdx = mid.indexOf(rootEle); // 左子树长度，左子树是中序遍历的 0~rootIdx-1 范围，长度为 rootIdx int leftLen = rootIdx; // 如果存在左子树，即左子树长度大于 0 if (leftLen > 0) { // 则从后序遍历中，截取出左子树的后序遍历 String leftPost = post.substring(0, leftLen); // 从中序遍历中，截取出左子树的中序遍历 String leftMid = mid.substring(0, rootIdx); // 将左子树的后、中遍历序列加入执行队列 queue.addLast(new String[] {leftPost, leftMid}); } // 如果存在右子树，即右子树长度大于 0 if (post.length() - 1 - leftLen > 0) { // 则从后序遍历中，截取出右子树的后序遍历 String rightPost = post.substring(leftLen, post.length() - 1); // 从中序遍历中，截取出右子树的中序遍历 String rightMid = mid.substring(rootIdx + 1); // 将右子树的后、中遍历序列加入执行队列 queue.addLast(new String[] {rightPost, rightMid}); } } }

#include <stdio.h> #include <stdlib.h> #include <string.h> /** 链表定义 **/ typedef struct ListNode { char post[27]; char mid[27]; struct ListNode *next; } ListNode; typedef struct LinkedList { int size; ListNode *head; ListNode *tail; } LinkedList; LinkedList *new_LinkedList() { LinkedList *link = (LinkedList *)malloc(sizeof(LinkedList)); link->size = 0; link->head = NULL; link->tail = NULL; return link; } void addLast_LinkedList(LinkedList *link, char *post, char *mid) { ListNode *node = (ListNode *)malloc(sizeof(ListNode)); strcpy(node->post, post); strcpy(node->mid, mid); node->next = NULL; if (link->size == 0) { link->head = node; link->tail = node; } else { link->tail->next = node; link->tail = node; } link->size++; } ListNode *removeFirst_LinkedList(LinkedList *link) { if (link->size == 0) exit(-1); ListNode *removed = link->head; if (link->size == 1) { link->head = NULL; link->tail = NULL; } else { link->head = link->head->next; } link->size--; return removed; } // res 记录题解 char res[27]; int res_size = 0; /*! * 字符串截取（左闭右开） * @param s 字符串 * @param start 起始位置（包含） * @param end 结束位置（不包含） * @return 指定区间的子串 */ char *subString(char *s, int start, int end) { int len = end - start; char *tmp = (char *)calloc(len + 1, sizeof(char)); strncat(tmp, s + start, len); return tmp; } /*! * 本方法用于从后序遍历、中序遍历序列中分离出：根，以及其左、右子树的后序、中序遍历序列 * @param post 后序遍历结果 * @param mid 中序遍历结果 * @param queue BFS 的执行队列 */ void devideLR(char *post, char *mid, LinkedList *queue) { // 后序遍历的最后一个元素就是根 char rootEle = post[strlen(post) - 1]; // 将根加入题解 res[res_size++] = rootEle; // 在中序遍历中找到根的位置 rootIdx，那么该位置左边就是左子树，右边就是右子树 int rootIdx = strchr(mid, rootEle) - mid; // 左子树长度，左子树是中序遍历的 0~rootIdx-1 范围，长度为 rootIdx // 如果存在左子树，即左子树长度大于 0 if (rootIdx > 0) { // 则从后序遍历中，截取出左子树的后序遍历 char* leftPost = subString(post, 0, rootIdx); // 从中序遍历中，截取出左子树的中序遍历 char* leftMid = subString(mid, 0, rootIdx); // 将左子树的后、中遍历序列加入执行队列 addLast_LinkedList(queue, leftPost, leftMid); } // 如果存在右子树，即右子树长度大于 0 if (strlen(post) - 1 - rootIdx > 0) { // 则从后序遍历中，截取出右子树的后序遍历 char* rightPost = subString(post, rootIdx, strlen(post) - 1); // 从中序遍历中，截取出右子树的中序遍历 char* rightMid = subString(mid, rootIdx + 1, strlen(mid)); // 将右子树的后、中遍历序列加入执行队列 addLast_LinkedList(queue, rightPost, rightMid); } } int main() { char post[27]; char mid[27]; scanf("%s %s", post, mid); // 广度优先搜索的执行队列，先加入左子树，再加入右子树 LinkedList *queue = new_LinkedList(); // 层序遍历出来的元素存放在 res 中 devideLR(post, mid, queue); while (queue->size > 0) { ListNode* node = removeFirst_LinkedList(queue); devideLR(node->post, node->mid, queue); } puts(res); return 0; }

二叉树遍历：由后序与中序推导层序结果（多语言实现）