使用树按顺序遍历来确定是否是BST或堆

Question

给出了这些有序的遍历列表：
1. 53,1，64,23,3,29,17,2,9,19
2. 49,32,51,71,32,10,21,8,13,11,41,17

我需要确定这些列表中的每个列表是否表示有效的BST / min或max堆，或者没有。
我正试图弄清楚如何接近这个，但除了蛮勇于各种可能的选择，我无法弄清楚一个“聪明”的方式来解决这个问题。

我可以使用哪些指示灯，如果有的话或解决这一目标，这将是字母强迫每个选项？

Answer 1

它们都不能成为BST。BST的一阶遍历访问其键的非降低顺序中的顶点（通过诱导易于证明）。

要确定它们是否是堆积，请注意，通过您已经知道树的列表中的元素数量（堆是完全二进制树，最多为一到上级别，以及所有叶子最后一个级别包装在左侧）。然后，如果堆财产保持，则练习归结为按照遍历和检查的相同顺序写下给定的键。

在特定示例中，第一个序列不能是堆的按顺序遍历，因为生成的树将具有键 $ 23,11,53 $ 的路径（增加深度顺序）。 相同的参数适用于带有键 $ 71,32，49 $ 的路径的第二个序列。