本文共 1708 字，大约阅读时间需要 5 分钟。

前序遍历结果和此题很类似，不同点在于前序遍历得到的序列中，第一个数字是根节点的值

解法1：递归

递归思想：

​ ●终止条件：

//left > right:当左子树为空时，mid = left，传入函数会出现left > right的情况，这种情况返回true        //left = right与left = right - 1:任意一个或两个数可以构成二叉树的后序遍历，返回true        if(left >= right - 1)            return true;

​ ●递推工作

​ 序列的最后一个节点为根的值，从左开始遍历，连续的小于根值的序列就是左子树序列，连续的大于根值的序列就是右子树序列。如果index != right，说明不满足条件。

​ ●返回值

​ 一个序列是否合法，需要判断序列能否完整分成左子树、右子树和根(判断index == right)，并且左子树合法，右子树合法。

复杂度：

​ ●时间复杂度：O(N^{2)，每次递归减去一个根节点，需要O(N)轮，最差情况下退化为链表，每轮需要遍历所有节点，需要O(N)，所以最坏需要O(N}2)

​ ●空间复杂度：退化为链表时，需要N层递归，O(N)

代码：

class Solution {   public:    bool verifyPostorder(vector
   
    & postorder) {           return verifyPostorder_boundary(postorder, 0, postorder.size() - 1);    }    bool verifyPostorder_boundary(vector
    
     & postorder, int left, int right){           //left > right:当左子树为空时，mid = left，传入函数会出现left > right的情况，这种情况返回true        //left = right与left = right - 1:任意一个或两个数可以构成二叉树的后序遍历，返回true        if(left >= right - 1)            return true;        int root_val = postorder[right];        int index = left;        //此处获得左子树，遇到>=的就跳出        while(postorder[index] < root_val)            index++;        //mid将left和right隔为两个新的区间        int mid = index;        while(postorder[index] > root_val)            index++;        //如果没出错，index应该在right跳出循环，所以判断index == right        //新的左子树区间为[left, mid - 1]，因为index++所以mid要减去1        //新的右子树区间为[mid, right - 1]，因为right处为root，所以去掉        return index == right && verifyPostorder_boundary(postorder, left, mid - 1) &&                verifyPostorder_boundary(postorder, mid, right - 1);    }};
    
   

解法2：单调栈

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/