美文网首页剑指Offer-PHP实现
《剑指Offer》-33.二叉搜索树的后序遍历序列

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

作者: 懒人成长 | 来源:发表于2018-08-20 18:15 被阅读0次

    题干

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

    相关文章

      网友评论

        本文标题:《剑指Offer》-33.二叉搜索树的后序遍历序列

        本文链接:https://www.haomeiwen.com/subject/nroliftx.html