二叉搜索树的后续遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
单挑递增栈辅助，逆向遍历数组
// 单调递增栈辅助，逆向遍历数组。
var verifyPostorder = function (postorder) {
// 单调栈使用， 单调递增的单调栈
let stack = [];
// 表示上一个根节点的元素，这里可以把postorder的最后一个元素root看成无穷大节点的左孩子
let root = Number.MAX_VALUE;
// 逆向遍历，就是翻转的先序遍历
for (let i = postorder.length - 1; i >= 0; --i) {
// 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
if (postorder[i] > root) {
return false;
}
while (stack.length > 0 && postorder[i] < stack[stack.length - 1]) {
// 数组元素小于单调栈的元素了，表示往左子树左了，记录下上个根节点
// 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
root = stack.pop();
}
// 这个新元素入栈
stack.push(postorder[i]);
}
return true;
};
算法流程
算法流程：
-
初始化 : 单调栈stack，父节点值 root = +∞（初始值为无穷大，可把树的根节点看为此无穷大节点的左孩子）
-
倒叙遍历 postorder: 记每个节点为r【i】；
- 判断 : 若r【i】 > root，说明此后序遍历序列不满足二叉搜索树定义，直接返回false；
- 更新父节点root : 当栈不为空 且 r【i】< stack[stack.length - 1]时，循环执行出栈，并将出栈节点赋给root。
- 入栈 : 将当前节点r【i】入栈；
-
若遍历完成，则说明后序遍历满足二叉搜索树定义，返回true。
复杂度分析
- 时间复炸度O(N)：遍历postorder所有节点，各节点均入栈/出栈一次，使用O（N）时间。
- 时间复杂度O（N）：最差情况下，单调栈stack存储所有节点，使用O（N）额外空间。
作者：jyd
链接：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/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。