前言

已经刷了将近20道题，凭空想象出思路，还不通过想想前几道做题总结的经验。所以我觉得应该停下来去复习一下前面的题目，整理一下做题的套路。温故而知新。

后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。

二叉搜索树定义： 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。

题目描述

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

     5
    / \
   2   6
  / \
 1   3

示例 1：

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

示例 2：

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

解题思路

1. 根据 二叉搜索树 的性质，左子树的节点的值 < 根节点的值，右子树相反
2. 因此，根据 当前根节点的值，查询 第一个右子节点出现的下标，上一步中，左子树已经符合要求
3. 因此，判断右子树的大小 是否满足条件若都满足条件，则表示 当前根的二叉搜索树性质满足，于是，我们再来 递归判断 其 左右子树是否满足

AC代码

var verifyPostorder = function(postorder) {
    let len = postorder.length;
    if(len <2) return true; // 只有一个元素必为后序遍历
    let root = postorder[len-1];// 后序遍历的最后一个元素为根节点
    let i = 0;
    for(;i < len -1; i++) {
        if(postorder[i] > root){// 即为root 的右子树
            break;
        }
    }
    // 判断左子树是否都小于root
    let result = postorder.slice(i, len - 1).every(item => item > root);
    if(result){ // 进行递归, 判断root的左右子树是否满足二叉树的性质。
        return verifyPostorder(postorder.slice(0,i)) && verifyPostorder(postorder.slice(i,len-1))
    }
    else {
        return false;
    }
};

总结:

二叉搜索树定义： 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。 本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情