《剑指Offer》-33.二叉搜索树的后序遍历序列

题干

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回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]));