前言🌧️

算法，对前端人来说陌生又熟悉，很多时候我们都不会像后端工程师一样重视这项能力。但事实上，算法对每一个程序员来说，都有着不可撼动的地位。

因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。

当然，学习也是有侧重点的，作为前端我们不需要像后端开发一样对算法全盘掌握，有些比较偏、不实用的类型和解法，只要稍做了解即可。

题目🦀

剑指 Offer 33. 二叉搜索树的后序遍历序列

难度中等

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

5
    / \
   2   6
  / \
 1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

1. 数组长度 <= 1000

解题思路🌵

• ⚠️这是二叉搜索树，它的特点是左边的子节点都必须小于根节点的值，右边的子节点都必须大于根节点的值
• 后续遍历，左右根的遍历顺序，由此数组的最后一位就为根节点，再将大问题拆分为小问题去解决，采用分而治之的思想
• 递推公式：获取当前数组的最后一个节点值，为中间节点，获取中间节点（值大于中间节点），根据中间节点分别获取左右子树，如果有中间节点，表示有左右子树，分别判断是否大于或小于中间节点⚠️当mid==-1时，表示没有找到中间节点，这左右子树总共只有2个节点的情况则肯定是没有右边节点，全是为左节点的情况
• 退出条件：当前节点数量小于2，表示只有一个节点的情况，无论怎样都符合后续遍历

解法🔥

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {
     if (postorder.length < 2) return true;
    const root=postorder.pop()
    const mid=postorder.findIndex((number)=>{return number>root})
    //获取左子树
    let left=postorder.slice(0,mid)
    //获取右子树
    let right=postorder.slice(mid)
    let result=left.every((item)=>item<root)&&right.every((item)=>item>root)   
    //这一步用来判断当前节点左右子树只有2个节点的情况
      if(mid==-1){
        result=true;
        right=[];
        left=postorder.slice(0)
    }
    return result&&verifyPostorder(left)&&verifyPostorder(right)
};

时间复杂度：O(n)

空间复杂度：O(n)

结束语🌞

那么鱼鱼的LeetCode算法篇的剑指Offer-33二叉搜索树的后序遍历序列⚡️就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。