二叉搜索树的后序遍历序列
解题思路：
-
后续遍历的顺序为 左->右->根，则数组的最后一位为根节点，寻找 第一个大于根节点 的节点，索引记为 inx，此时可划分出左子树区间 [0, inx - 1]、右子树区间 [inx, postorder.length - 1]；
-
二叉搜索树右子树值最小值永远大于左子树最大值、大于根节点；，前面根据找到的第一个大于根节点的值划分左右子树区间，所以左区间都小于根节点，则无需判断，只需要判断右节点的最小值是不是大于根节点即可；
-
所有子树都需正确才可判定正确，因此使用 与逻辑符 && 连接；
复杂度：
-
时间复杂度：O(N^2)，每次调用 recur(i,j) 减去一个根节点，因此递归占用 O(N)，最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N)；
-
空间复杂度：O(N)，最差情况下（即当树退化为链表），递归深度将达到 N；
代码实现：
function verifyPostorder(postorder: number[]): boolean {
// 终止条件，树节点 <=2 返回 true
if (postorder.length <= 2) return true;
// 根节点
const root = postorder[postorder.length - 1];
// 寻找 第一个大于根节点 的节点 inx
const idx = postorder.findIndex((item) => item > root);
// 划分出：左子树区间 [left, inx - 1]
const left = postorder.slice(0, idx);
// 划分出：右子树区间 [inx, postorder.length - 1]
const right = postorder.slice(idx, -1);
// 二叉搜索树的右子树和根相比，最小值一定是根值
// 因为前面根据找到的第一个大于根节点的值，所以左区间都小于根节点，无需判断
if (Math.min(root, ...right) !== root) return false
return verifyPostorder(left) && verifyPostorder(right)
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
剑指 Offer 07.重建二叉树
上一篇
评论
