algorithm - 从前序和后序遍历中绘制树而不对树的形状做任何假设

Question

在我的考试中，我遇到了以下问题:

(a) 非常简单，但是对于 (b)，我完全糊涂了。不做假设是什么意思？如果我不假设它是一个二叉树，我该如何解决它(因为前序和后序与 BST 相关)？不假设它是 BST，我不知道如何开始？

你能指导我吗？

Answer 1

b) 那么，这些顺序看起来与二叉树顺序一致:

V W B C Y Z N A M L P
C B Z N Y W M P L A V

首先，请注意根是 V，因为它既在前序中排在首位又在后序中排在最后:

V W B C Y Z N A M L P
  C B Z N Y W M P L A V

再看W和A，分别是根的第一个左 child 和最后一个右 child 。前序中的A标记了遍历从根的左子树过渡到根的右子树的地方。后序中的 W 标记相同的位置。注意，拆分遍历时，A和W是相邻的位置:

V W B C Y Z N    A M L P
  C B Z N Y W    M P L A V

现在你需要为序列解决同样的问题:

W B C Y Z N    
C B Z N Y W

和

A M L P
M P L A

例如，第一个序列的下一步是:

W B C    Y Z N    
  C B    Z N Y W

希望这对您有所帮助。