共计 2682 个字符，预计需要花费 7 分钟才能阅读完成。
题目
输出一个整数数组，判断该数组是不是某二叉搜寻树的后序遍历后果。如果是则返回 true，否则返回 false。假如输出的数组的任意两个数字都互不雷同。
参考以下这颗二叉搜寻树：
示例 1：
输出: [1,6,3,2,5]
输入: false
示例 2：
输出: [1,3,2,6,5]
输入: true
准备知识点
二叉树的遍历
二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历，这三种遍历能够用递归实现，也可应用非递归实现。
前序遍历：根节点 -> 左子树 -> 右子树（根 -> 左 -> 右）
中序遍历：左子树 -> 根节点 -> 右子树（左 -> 根 -> 右）
后序遍历：左子树 -> 右子树 -> 根节点（左 -> 右 -> 根）
1. 前序遍历
前序的遍历的特点，根节点 -> 左子树 -> 右子树，留神看前序的遍历的代码 printf 语句是放在两条递归语句之前的，所以先 拜访根节点 G，打印 G ，而后拜访左子树 D，此时左子树 D 又作为根节点，打印 D，再拜访 D 的左子树 A
A 又作为根节点，打印 A， A 没有左子树或者右子树，函数调用完结返回到 D 节点（此时曾经打印进去的有：GDA）D 节点的左子树曾经递归实现，当初递归拜访右子树 F，F 作为根节点，打印 F， F 有左子树拜访左子树 E，E 作为
根节点，打印 E，（此时曾经打印进去的有：GDAFE），E 没有左子树和右子树，函数递归完结返回 F 节点，F 的左子树曾经递归实现了，但没有右子树，所以函数递归完结，返回 D 节点，D 节点的左子树和右子树递归全副实现，
函数递归完结返回 G 节点，拜访 G 节点的右子树 M，M 作为根节点，打印 M，拜访 M 的左子树 H，H 作为根节点，打印 H，（此时曾经打印进去的有：GDAFEMH）H 没有左子树和右子树，函数递归完结，返回 M 节点，M 节点的左子树曾经
递归实现，拜访右子树 Z，Z 作为根节点，打印 Z， Z 没有左子树和右子树，函数递归完结，返回 M 节点，M 节点的左子树右子树递归全副实现，函数递归完结，返回 G 节点，G 节点的左右子树递归全副实现，整个二叉树的遍历就完结了
前序遍历后果：GDAFEMHZ
总结一下前序遍历步骤
第一步：打印该节点
第二步：拜访左子树，返回到第一步（留神：返回到第一步的意思是将根节点的左子树作为 新的根节点，就好比图中 D 是 G 的左子树然而 D 也是 A 节点和 F 节点的根节点）
第三步：拜访右子树，返回到第一步
第四步：完结递归，返回到上一个节点
前序遍历的另一种表述：
（1）拜访根节点
（2）前序遍历左子树
（3）前序遍历右子树
（在实现第 2,3 步的时候，也是要依照前序遍历二叉树的规定实现）
2. 中序遍历（具体遍历过程就不再赘述了，(┬_┬)）
第一步：拜访该节点左子树
第二步：若该节点有左子树，则返回第一步，否则打印该节点
第三步：若该节点有右子树，则返回第一步，否则完结递归并返回上一节点
（按我本人了解的中序就是：先左到底，左到不能在左了就停下来并打印该节点，而后返回到该节点的上一节点，并打印该节点，而后再拜访该节点的右子树，再左到不能再左了就停下来）
中序遍历的另一种表述：
（1）中序遍历左子树
（2）拜访根节点
（3）中序遍历右子树
（在实现第 1，3 步的时候，要依照中序遍历的规定来实现）
所以该图的中序遍历为：ADEFGHMZ
3. 后序遍历步骤
第一步：拜访左子树
第二步：若该节点有左子树，返回第一步
第三步：若该节点有右子树，返回第一步，否则打印该节点并返回上一节点
后序遍历的另一种表述：
（1）后序遍历左子树
（2）后序遍历右子树
（3）拜访根节点
（在实现 1,2 步的时候，仍然要依照后序遍历的规定来实现）
该图的后序遍历为：AEFDHZMG
网上多找一些重构二叉树的练习题，有助于加深了解上述三种遍历树的过程
重要概念
二叉搜寻树特色：左子树小于根节点小于右子树
题解思路
了解上述知识点后，回顾题目，既然是后序遍历，那么，数组最初一个肯定是根节点，例如给你 [1,3,2,6,5] 这个数组，那么 5 就是根节点，依照二叉搜寻树的特色，1，3 就是左子树，2，6，5 就是右子树。同时每个子树也要满足上诉条件，自然而然就想到递归查找判断了。明确了这些原理后，用代码实现就很容易了。
代码实现
/**
* @param {number[]} postorder
* @return {boolean}
*/
var verifyPostorder = function(postorder) {if (!postorder.length) return true; // 如果没有子树了，返回 true
const root = postorder[postorder.length - 1]; // 后续遍历后果的最初一位是树的根节点
// 根节点的左子树全副小于根节点，根节点的右子树全副大于根节点
const leftTree = [], rightTree = []; // 缓存以后节点的左子树和右子树，用于下次递归查问判断
let cIndex = null; // 记录左右子树的分界点，即第一个满足右子树的节点，因为左右子树要离开递归查
const flag = postorder.every((item, index) => {if (index === postorder.length - 1) return true; // 根节点不判断
if (cIndex === null && item > root) {cIndex = index; // 记录第一个遇到大于根节点的右子树节点，作为分界线}
if (cIndex !== null) { // 如果 cIndex !== null，阐明曾经遍历到右子树的节点了，那就要依照右节点的规定判断接下去的树（右子树的值全都要大于根节点），并且把之后的节点 push 到右子树的数组，用于递归
if (index >= cIndex) {rightTree.push(item);
return item > root;
}
} else { // 如果 cIndex === null 就说名没有遇到右子树的节点，那就判断左子树的特色，左子树的节点都要小于根节点
leftTree.push(item);
return item < root;
}
})
if (!flag) return false; // 以后节点都没有满足搜寻的特色，那就间接返回 false 了
let left = true, right = true;
if (leftTree.length) {left = verifyPostorder(leftTree); // 递归查问判断左子树是否满足二叉搜寻树的特色
}
if (rightTree.length) {right = verifyPostorder(rightTree); // 递归查问判断右子树是否满足二叉搜寻树的特色
}
return left && right; // 左右都满足二叉搜寻树的特色，才会返回 true
};
