• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

JZ23 二叉搜索树的后序遍历序列

开发技术 开发技术 7天前 4次浏览

二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解题思路
二叉搜索树:左子树的元素是都小于根元素,右子树都大于根元素
后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,所以数组最后一个元素是根元素。
从前面开始遍历,小于的当前根元素的值是左子树的,当找到第一个大于当前根元素的值,可以确定后半段的元素都应是在当前节点的右子树
如果后半段(右子树)里面有小于根元素的值的元素,就说明这个不是二叉搜索树的后序遍历。最后循环校验每个子树是否也满足二叉搜索树的后序遍历即可。

func helper(sequence []int, start, end int) bool {
    if start > end {
        return true
    }
    var i int
    for i = start; i < end; i++ {
        if sequence[i] > sequence[end] {
            break
        }
    }
    
    for j := i; j < end; j++ {
        if sequence[j] < sequence[end] {
            return false
        }
    }
    return helper(sequence, start, i - 1) && helper(sequence, i, end - 1)
}

func VerifySquenceOfBST( sequence []int ) bool {
    if len(sequence) == 0 {
        return false
    }
    return helper(sequence, 0, len(sequence) - 1)
}

 


程序员灯塔
转载请注明原文链接:JZ23 二叉搜索树的后序遍历序列
喜欢 (0)