根据后序数组重建搜索二叉树

[编程题]根据后序数组重建搜索二叉树

热度指数：1993 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个有 n 个不重复整数的数组 arr，判断 arr 是否可能是节点值类型为整数的搜索二叉树后序遍历的结果。

输入描述:

第一行一个整数 n，表示数组的长度。

第二行 n 个整数 arr_i。

输出描述:

如果是搜索二叉树后序遍历的结果则输出 "true"，否则输出 "false"。

示例1

输入

3
1 3 2

输出

true

备注:

算法知识视频讲解

Python 3

毓毓子最可爱

#判断当前序列是否是二叉搜索树后序遍历
#二叉搜索树的特点是左子树小于根，右子树大于根
#而后序遍历是左右根的顺序
#所以序列应该是从小到大的顺序
def isBST(nums, low, high) -> bool:
    #叶节点
    if low >= high:
        return True
    #根节点
    last = nums[high]
    i = 0
    #找到右子树入口
    for i in range(low, high):
        if nums[i] > last:
            break
    #在右子树中判断
    #右子树中的节点值应该是大于根节点值的
    for j in range(i + 1, high):
        #违反了规定
        #一定不是
        if nums[j] < last:
            return False
    #分别在两棵子树中递归进行判断
    return isBST(nums, low, i - 1) and isBST(nums, i, high - 1)

n = eval(input())
nums = list(map(int, input().split()))
rlt = isBST(nums, 0, len(nums) - 1)
if rlt:
    print('true')
else:
    print('false')

发表于 2021-08-05 09:13:26 回复(0)