Day15:二叉树的后续遍历序列
请实现一个函数来判断整数数组 postorder
是否为二叉搜索树的后序遍历结果。
示例 1:
输入: postorder = [4,9,6,5,8] 输出: false 解释:从上图可以看出这不是一颗二叉搜索树
LCR 152. 验证二叉搜索树的后序遍历序列 - 力扣(LeetCode)
class Solution {
public boolean verifyTreeOrder(int[] postorder) {
if(postorder == null || postorder.length == 0 || postorder.length == 1){
return true;
}
int length = postorder.length - 1;
int root = postorder[length];
int index = 0;
//遍历出左子树节点
for(int i = 0; i < length; i++){
if(postorder[i] > root){
index = i;
break;
}
}
if (index == 0 && postorder[index] < root) {
index = length; // 右子树为空
}
//从这开始都应该是比根大了
for(int j = index; j <length; j++ ){
if(postorder[j] < root)
return false;
}
// 处理左子树
int[] left = new int[0]; // 默认左子树为空
if (index > 0) {
left = Arrays.copyOfRange(postorder, 0, index);
}
// 处理右子树
int[] right = new int[0]; // 默认右子树为空
if (index < length) {
right = Arrays.copyOfRange(postorder, index, length);
}
return verifyTreeOrder(left)&&verifyTreeOrder(right);
}
}
要注意函数调用的边界。Arrays.copyOfRange(postorder, 0, index)
是复制从索引 0
到 index - 1
的元素,而不是复制到 index
。在这里栽坑了。然后就是右子树为空的情况,因为没有比他大的元素,所以index不会变,deepseek让我加一个判断,我觉得应该是我代码本身的纰漏。选择把index的更新放在判断体的外面就行了(基本功不好)
class Solution {
public boolean verifyTreeOrder(int[] postorder) {
if(postorder == null || postorder.length == 0 || postorder.length == 1){
return true;
}
int length = postorder.length - 1;
int root = postorder[length];
int index = 0;
//遍历出左子树节点
for(; index < length; index++){
if(postorder[index] > root){
break;
}
}
for(int j = index; j <length; j++ ){
if(postorder[j] < root)
return false;
}
// 处理左子树
int[] left = new int[0]; // 默认左子树为空
if (index > 0) {
left = Arrays.copyOfRange(postorder, 0, index);
}
// 处理右子树
int[] right = new int[0]; // 默认右子树为空
if (index < length) {
right = Arrays.copyOfRange(postorder, index, length);
}
return verifyTreeOrder(left)&&verifyTreeOrder(right);
}
}