数据结构与算法之栈: LeetCode LCR 152. 验证二叉搜索树的后序遍历序列 (Ts版)

验证二叉搜索树的后序遍历序列

• https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/description/

描述

• 请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果

示例 1

输入: postorder = [4,9,6,5,8]
输出: false

解释：从上图可以看出这不是一颗二叉搜索树

示例 2

输入: postorder = [4,6,5,9,8]
输出: true 

解释：可构建的二叉搜索树如上图

提示

• 数组长度 <= 1000
• postorder 中无重复数字

Typescript 版算法实现

1 ) 方案：递归分治

function verifyTreeOrder(postorder: number[]): boolean {function recur(postorder: number[], i: number, j: number): boolean {if (i >= j) return true;let p = i;// 找到第一个大于根节点（postorder[j]）的位置while (postorder[p] < postorder[j]) p++;const m = p;// 检查右子树是否都大于根节点while (postorder[p] > postorder[j]) p++;// 递归检查左子树和右子树，并且确保所有元素都被检查过return p === j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);}return recur(postorder, 0, postorder.length - 1);
}

2 ）方案2：递归优化

function verifyTreeOrder(postorder: number[]): boolean {if (postorder.length <= 2) return true// 最后一个是root节点const root = postorder.pop()let i = 0// 找到左右的分界点while (postorder[i] < root) {i++}let right = postorder.slice(i)let left = postorder.slice(0, i)// 右边当中所有节点都大于rootconst rightResult = right.every((item) => item > root)//递归return rightResult && verifyTreeOrder(left) && verifyTreeOrder(right)
}

3 ）方案3：辅助单调栈

function verifyTreeOrder(postorder: number[]): boolean {const stack: number[] = [];let root: number = Number.MAX_SAFE_INTEGER;for (let i = postorder.length - 1; i >= 0; i--) {if (postorder[i] > root) return false;while (stack.length > 0 && stack[stack.length - 1] > postorder[i]) {root = stack.pop()!;}stack.push(postorder[i]);}return true;
}