如何识别某个二叉搜索树遍历属于后序还是中序？

Question

如果一个二叉搜索树的前序遍历是 [P, A, R, S]，如何确定 [R, S, A, P] 是中序遍历还是后序遍历？ 如果是后序遍历，如何确定它是 (左子树，右子树，根节点) 还是 (右子树，左子树，根节点)？

- SajjadSM

---

以编程方式？那么只需从输入数据构建该树，然后使用“中序”/“后序”遍历它并获取结果即可。它的时间复杂度为O(n)。 - libik

你能写出代码吗？我们可以帮助你。如何识别[R，S，A，P]属于中序遍历还是后序遍历？-使用先序遍历和二叉搜索树的属性构建树。然后进行中序遍历和后序遍历，与[R，S，A，P]匹配的顺序即为它所属的顺序。 - nice_dev

Answer 1

二叉搜索树的顺序始终是有序的。由于[R，S，A，P]不是有序的，因此它应该是后序。

- learner

---

现在如何查找是（左，右，根）还是（右，左，根）？ - SajjadSM

@S.Safari，这是一个现在可以搜索到的标准问题。 - Shashwat Kumar

Answer 2

如果先序遍历是[P, A, R, S]，那么P必须是根节点。由于它是二叉搜索树，所以A必须是左子节点，而R和S必须在右子树中。这给你两棵可能的树：

      P                 P
    A   R            A     S
          S              R

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

- Jim Mischel