方法一：划分左右子树并递归
后序遍历的序列中，根一定在最后一个。
除了根以外，其他元素，左子树的序列在前，右子树在后，而且左子树元素一定都小于根，右子树一定都大于。
根据这个可以把这个数组分成三部分：根，左子树，右子树。然后递归判断，直到分成长度为 1 的数组，自然满足条件。递归过程中，如果有不满足条件的就返回 False。
时间复杂度：O(n^2)
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def verify(l, r):
if l >= r: return True
v = postorder[r]
i = l
while postorder[i] < v:
i += 1
mid = i
while postorder[i] > v:
i += 1
return i == r and verify(l, i-1) and verify(i, r-1)
return verify(0, len(postorder)-1)方法二：单调栈
从后往前看这个数组，最后一个元素是根，然后是右子树，左子树。
根 -> 右子树，元素值应该越来越大。大的值都压入栈中，这个栈就是递增的。
当遇到一个值小于的时候，说明到了某个左子树。这时开始 pop 栈中的元素，直到拿出一个小于当前元素的值，这个值就是当前元素的父亲。这时就把 root 设为这个值，然后需要保证这个左子树上的元素都小于这个根，如不满足就返回 False。
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
s, root = [], float('+inf')
for v in postorder[::-1]:
if v > root:
return False
while s and s[-1] > v:
root = s.pop()
s.append(v)
return True
