algorithm - 如何识别一些二叉搜索树遍历是后序还是中序？

Question

如果一棵二叉搜索树的前序是[P,A,R,S]，如何识别[R,S,A,P]是中序还是后序？ 如果是后序怎么判断是(Left, Right, Root)还是(Right, Left, Root)？

Answer 1

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

      P                 P
    A   R            A     S
          S              R

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