剑指 Offer 33. 二叉搜索树的后序遍历序列
本问题对应的 leetcode 原文链接:剑指 Offer 33. 二叉搜索树的后序遍历序列
本次对应打卡问题:【二叉树专题】剑指 Offer 33. 二叉搜索树的后序遍历序列
问题描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/ \
2 6
/ \
1 3
示例1 :
输入: [1,6,3,2,5]
输出: false
示例2 :
输入: [1,3,2,6,5]
输出: true
- 提示:
数组长度 <= 1000
解题思路
视频讲解直达: 本题视频讲解
代码实现
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder == null){
return true;
}
return f(postorder, 0, postorder.length - 1);
}
boolean f(int[] postorder, int i, int j){
if(i >= j){
return true;
}
int root = postorder[j];
int p = i;
// 获取第一个大于或者等于 root 等元素的位置
while(postorder[p] < root) p++;
// 判断 p ~ j -1 这个范围是否存在小于root的元素
for(int k = p; k < j; k++){
if(postorder[k] < root){
return false;
}
}
return f(postorder, i, p - 1) && f(postorder, p, j - 1);
}
}
- 时间复杂度:最差O(n^2)
- 空间复杂度:最差(n)(退化成链表)
评论(2)
递归的去判断,后序遍历中的最后一个节点是根节点,二叉搜索树又有左 > 右的特点,时间复杂度0n^2 空间复杂度on
是左子树根节点<右子树根节点吧