已知二叉树的后序遍历序列和中序遍历序列,怎样求其前序遍历序列？

精选

推荐答案 2020-01-05

这类型的题目是先根据后序的遍历顺序，快速找到根节点，后序肯定是最后一个结点e,找到根节点之后，查看根节点在中序中的位置，中序的遍历顺序是左根右，所以中序中e左边是e的左子树上的结点，右边是右子树上的结点。
依照上述规则找左子树的根节点，在后序中查看，b是e的右子树根节点，a是左子树的根节点.依次类推，最终二叉树得到如下：
1.

e
2.

/

\
3.

a

b
4.

/

\
5.

c

d
这样前序也很容易得到了，eacdb

温馨提示：答案为网友推荐，仅供参考

当前网址：http://11.wendadaohang.com/zd/FS8748M278728Mv4q2M.html

相似回答

已知二叉树的中序序列,后序序列,怎么求前序序列答：确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。递归求解树。将左子树和右子...