如何识别一些二叉搜索树的遍历是post-order还是in-order？

Question

如果一棵二叉搜索树的前序是[P,A,R,S]，如何识别[R,S,A,P]是中序还是post-命令？ 如果是post-order怎么找出是(Left, Right, Root)还是(Right, Left, Root)?

Answer 1

二叉搜索树的顺序总是有序的。由于[R,S,A,P]没有排序，所以应该是post的顺序。

Answer 2

如果前序遍历是[P,A,R,S]，那么P一定是根。既然是二叉搜索树，那么A一定是左子树，R和S一定在右子树中。这给了你两种可能的树：

      P                 P
    A   R            A     S
          S              R

第二棵树的反向 post 顺序遍历将提供序列 [R, S, A, P]。