面试题33.二叉搜索树的后序遍历序列方法一：在划分左右子树和递归后序遍历的序列中，根必须在最后。除了根，其他元素的顺序都是左子树在前，右子树在后，且左子树的元素一定比根小，右子树的元素一定比根大。据此，数组可以分为三部分：根、左子树、右子树。然后递归判断，直到分成长度为1的数组，自然满足条件。在递归过程中，如果不满足任何条件，则返回False。时间复杂度：O(n^2)类解决方案：defverifyPostorder(self,postorder:List[int])->bool:defverify(l,r):ifl>=r:returnTruev=postorder[r]i=lwhilepostorder[i]v:i+=1返回i==randverify(l,i-1)andverify(i,r-1)returnverify(0,len(postorder)-1)方法二：单调栈从后往前看数组，最后一个元素为根，然后是右子树，再是左子树。Root->右子树，元素值应该越来越大。大值入栈，栈自增。当遇到小于的值时，表示已经到达某个左子树。此时开始弹出栈中的元素，直到取出一个小于当前元素的值，即为当前元素的父元素。此时设置root为这个值，然后需要保证左子树上的元素都小于这个root，不满足则返回False。类解决方案：defverifyPostorder(self,postorder:List[int])->bool:s,root=[],float('+inf')forvinpostorder[::-1]:ifv>root:returnFalsewhilesands[-1]>v:root=s.pop()s.append(v)returnTrue参考：https://leetcode-cn.com/probl...
