vivo|算法：二叉搜索树的后序遍历序列智能手机|小米科技

文章图片

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true ，否则返回 false 。假设输入的数组的任意两个数字都互不相同。
【vivo|算法：二叉搜索树的后序遍历序列】参考以下这颗二叉搜索树：
5
/ \\
2 6
/ \\
1 3
示例

提示

方法：递归分治后序遍历：
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：【遍历左子树|遍历右子树|访问根结点】。
二叉搜索树：
在二叉搜索树中：

代码如下：

复杂度分析

时间复杂度：O(N的2次方) ，每次调用 compare(ij) 减去一个根节点，因此递归占用 O(N) ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N)。
空间复杂度：O(N) ，最差情况下（即当树退化为链表），递归深度将达到 N。

END世上无难事，只要肯攀登，赠友人。
本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！
好兄弟可以点赞并关注我，全部都是干货。