题解 | #二叉搜索树的后序遍历序列#
二叉搜索树的后序遍历序列
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd
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
上次被挂了后我连简历都不刷了