python3，非递归方法。
理解：
所谓后序遍历，尾部一定是最“中”性的。
体现在BST中，即任意尾部，相对于该尾部之前，一定是中等大小的，等价表述：对于任意尾部，最多，经过一轮小于尾部的迭代，再经过一轮大于尾部的迭代，就一定可以到达尾部。
BST一定满足这个特征，满足这个特征的一定可以做成BST。
class Solution: def VerifySquenceOfBST(self , sequence: List[int]) -> bool: if not sequence: return False i = 0 size = len(sequence)-1 while size: while sequence[i] < sequence[size]: # 一轮小于尾部的迭代 i = i + 1 while sequence[i] > sequence[size]: # 一轮大于尾部的迭代 i = i + 1 if i < size: return False # 若到达尾部，则该尾部暂时满足。否则直接False i = 0 size = size - 1 return True
京公网安备 11010502036488号