二叉树遍历中前序序列、中序序列和后序序列之间的关系相关的问题

Question

大伙都知道二叉树的遍历是四种，先序遍历，中序遍历，后序遍历和层次遍历。那么问题来了：
为什么说前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序？
既然前序序列和中序序列的本质相当于入栈出栈了，那么后序序列和中序序列是否也有差不多的关系呢？前序序列和后序序列是否有什么关系呢？
题主知道二叉树遍历的非递归模式，也就是借助栈或者是队列进行判空循环的操作，但是前序遍历和中序遍历的非递归模式也只是visit()函数在不一样的位置罢了，本质上的函数还是相同的。

Answer 1

关于前序序列和中序序列的关系，前序遍历的顺序是：根节点、左子树、右子树。中序遍历的顺序是：左子树、根节点、右子树。所以如果把前序遍历的序列看成一个栈，并按照前序遍历的顺序将节点压入栈中，那么在遍历完左子树后，根节点就会位于栈顶，而在中序遍历中，根节点是在遍历完左子树后才会访问的。所以可以按照中序遍历的顺序将节点从栈中弹出，从而得到一个和中序遍历相同的序列。这就是为什么说前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序的原因。

至于后序序列和中序序列的关系，后序遍历的顺序是：左子树、右子树、根节点。如果把后序遍历的序列看成一个栈，并按照后序遍历的顺序将节点压入栈中，那么在遍历完左子树后，可以看到，根节点位于栈底，而在中序遍历中，根节点是在遍历完左子树和右子树之后才会访问的。所以可以按照中序遍历的顺序将节点从栈中弹出，从而得到一个和中序遍历相同的序列。

至于前序序列和后序序列的关系，由于前序序列的顺序是：根节点、左子树、右子树，而后序序列的顺序是：左子树、右子树、根节点，所以前序序列和后序序列没有直接的关系。但是可以通过中序序列来建立前序序列和后序序列之间的关系。可以先根据前序序列和中序序列建立一颗二叉树，然后再按照树的前序遍历顺序遍历整棵树，得到的序列就是后序序列。这是因为，在二叉树的前序遍历中，根节点是最后一个被访问的，而在二叉树的后序遍历中，根节点是第一个被访问的。
仅供参考，望采纳。