Question

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为?

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为

Answer 1

已知一棵二叉树前序遍和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历是DGEBHFCA。

前序遍历的第一个节点为根节点，由前序遍历可知，A为根节点。中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBGE。去掉根节点和左子树节点，右子数节点为CHF。前序遍历的第二个节点为B，由2知B为左子树节点，所以B为左子树的根节点。

由前序遍历，DEG在B节点下面，由中序遍历，D是B的左节点，GE是B的右节点。由前序遍历，E是G的根节点，由中序遍历，G是E的左子节点。由前序遍历，C是二叉树的右根节点，由中序遍历，C不含左子节点，HF为C的右子节点。由前序遍历，F为H的根节点，由中序遍历，H为F的左子节点。

在二叉树中，求后序遍历，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。

扩展资料：

先序遍历2113的第一个结点是根结点，所以5261A是根，然后在中序遍历中4102找到A，（DBGE）A（CHF），由中序遍1653历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。

然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CHF，C是根，HF是右子树的中序遍历。

因为仍然有没划分完的部分，所以继续看先序。对于BDEG，B是根已知，D是整个左子树已知，所以EG是右子树的先序遍历，E是右根，再对照中序可知G是E的左子树，CHF同理。

Answer 2

后序：DGEBHFCA

追问

具体过程怎么来的？

追答

前序遍历顺序：根节点，左孩子节点，右孩子节点
中序遍历顺序：左孩子节点，根节点，右孩子节点

由前序遍历可以看出，该树根节点为A
从中序遍历中，可将整棵树按根节点分为左子树，包括DBGE四个节点；右子树包括CHF三个节点
再从前序遍历的顺序分析出，B为A左孩子节点，C为A右孩子节点，再逐一节点分析，即可得该树：
A
╱ ╲
B C
╱ ╲ ╲
D E F
╱ ╱
G H