经典数据结构：二叉树遍历，前序中序后序一次搞清楚

题型

  • 知前序中序，得后序
  • 知后序中序，得前序

（注：仅知前序后序，无法确定中序，因为不知道左右子树。）

特征

以仅三个节点的最小二叉树遍历为例，涵盖根节点+左叶节点+右叶节点，总结如下：

  • 前序，根左右
  • 中序，左根右
  • 后序，左右根

关键思路

关键是靠中序，确定某个根节点左右的子树堆。然后靠前序或后序来确定其中一侧的子树根节点。

  • 后序从后往前看节点，从根节点的右子树开始，然后往左子树靠
  • 前序从前往后看节点，从根节点的左子树开始，然后往右子树靠

例题

自行练习，画出二叉树，知其二，得其一。

题1：

前序，EBCD
中序，BDCE
后序，DCBE

题2：

前序，CEDBA
中序，DEBAC
后序，DABEC

题3：

前序，HGEDBFCA
中序，EGBDHFAC
后序，EBDGACFH