1. 题目描述
输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
2. 题目分析
- 题目给的是一个二叉搜索树后序遍历的数组
- 二叉搜索树特点：左子树
- 后序遍历的特点：最后一个数是根节点（root）
- 我们首先验证极端情况：该数组为空，返回false。我们找到数组最后一个数字，也就是根节点，找出该后序遍历序列中左右子树的交叉点。
if (sequence == null || sequence.length == 0) { return false; } int root = sequence[sequence.length - 1]; int i = 0; for (i = 0; i < sequence.length - 1; i++) { if (sequence[i] > root) { break; } }
- 判断右子树是否大于根节点（root）
for (j = i; j < sequence.length - 1; j++) { if (sequence[j] < root) { return false; } }
- 将左右子树分开，分别进行上述的操作
if (i > 0) { left = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i)); } if (j < sequence.length - 1) { right = VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length - 1)); }
- 关于Arrays.copyOfRange(T[ ] original,int from,int to):将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。 注意这里包括下标from，不包括上标to。
3. 题目代码
/* * 输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 * Arrays.copyOfRange(T[ ] original,int from,int * to):将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。 注意这里包括下标from，不包括上标to。 */ public boolean VerifySquenceOfBST(int[] sequence) { if (sequence == null || sequence.length == 0) { return false; } int root = sequence[sequence.length - 1]; int i = 0; for (i = 0; i < sequence.length - 1; i++) { if (sequence[i] > root) { break; } } int j = i; for (j = i; j < sequence.length - 1; j++) { if (sequence[j] < root) { return false; } } boolean left = true; boolean right = true; if (i > 0) { left = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i - 1)); } if (j < sequence.length - 1) { right = VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length - 1)); } return (left && right); }
