请实现一个函数来判断整数数组 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);}
}
