题干
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。
解题思路
二叉搜索树的特点是根节点的值大于所有左子树的节点值，小于所有右子树的节点值，后序遍历的规则是 左子树->右子树->根，因此，给定数组的最后一个元素必然是根节点，判断该节点是否能将数组分成符合二叉搜索树规则的两部分，如果不能，则返回false，否则递归调用，知道无法分隔为止。
代码实现
<?php
function verifySequenceOfBST($sequence)
{
if (empty($sequence)) {
return false;
}
$count = count($sequence);
$root = $sequence[$count - 1];
for ($i = 0; $i < $count - 1; $i++) {
if ($sequence[$i] > $root) {
break;
}
}
for ($j = $i; $j < $count - 1; $j++) {
if ($sequence[$j] < $root) {
return false;
}
}
$isLeftValid = true;
if ($i > 0) {
$isLeftValid = verifySequenceOfBST(array_slice($sequence, 0, $i));
}
$isRightValid = true;
if ($j > 0) {
$isRightValid = verifySequenceOfBST(array_slice($sequence, $i, $count - $i - 1));
}
return $isLeftValid && $isRightValid;
}
var_dump(verifySequenceOfBST([5, 7, 6, 9, 11, 10, 8]));
