根据序列构建二叉树 图解 文字详细解释

根据序列构建二叉树

题目：已知一棵二叉树，其先序序列为：ABDEGMNCFH，中序序列为：DBMGNEACHF，请画出这棵二叉树（给出过程），并给出其后序序列。

图解

后序遍历：DMNGEBHFCA

解题步骤

先：ABDEGMNCFH
中：DBMGNEACHF

1. 根据先序遍历知道 A 是根节点，由中序遍历知道 DBMGNE 是 A 的左子树，CHF 是A 的右子树。
2. 由 先序遍历 BDEGMN 知道 B是根节点，由中序遍历 DBMGNE 知道 D是B的左子树， MGNE是B的右子树。
3. 由 先序遍历 EGMN 知道 E是根节点，由中序遍历 MGNE 知道 MGN 是E的左子树，E没有右子树。
4. 由 先序遍历 GMN 知道 G 是根节点，由中序遍历 MGN 知道 M 是 G 的左子树，N 是 G 右子树。
5. 由 先序遍历 CFH 知道 C 是根节点，由中序遍历 CHF 知道 HF 是 C 右子树。
6. 由 先序遍历 FH 知道 F 是根节点，由中序遍历 HF 知道 H 是 F 左子树。