Question

请问下数据结构一个题目？

请问下数据结构一个题目？第13题，请问他的另一种解法中为什么说前序序列和中序序列的关系相当于以前序序列为入栈次序，中序序列为出栈次序？不懂这个意思？谢谢！





Answer 1

这两个问题考察的是不同方面：
前序序列和中序序列的关系相当于以前序序列为入栈次序，中序序列为出栈次序，原因是因为遍历都是通过递归得到的，递归需要用栈来完成，通过栈得不到的，遍历也得不到，事实上，n个元素进栈得到的不同序列数量就等于n个结点二叉树的形态
另外一个问题考察的二叉树遍历的性质，这个前序和后序正好相反，则是每一层只有一个结点，和那个栈关系有点远

追问

还是不明白这个意思，比如说a是根节点，bc是左右孩子，前序是abc,出栈应该是cba，但是中序是bca,怎么可能前序是入栈次序，中序是出栈次序，他是不是说错了？