【剑指offer】面试题24：二叉搜索树的兴许前序遍历序列

时间：2023-03-08 16:30:28

分析：

前序： 根 左 右

后序： 左 由 根

二叉搜索树： 左 < 根 < 右

那么这就非常明显了。

def ifpost(postArray, start, end):

	#one or "" is true

	if(end - start <= 1):

		return True

	i = start

	#left branch whose value < root

	while i <= end and postArray[i] < postArray[end]:

		i += 1

	#partion of left and right branch

	part = i

	#right branch whose value > root

	while i <= end and postArray[i] > postArray[end]:

		i += 1

	#not all right part > root

	if(i < end):

		return False

	return ifpost(postArray, start, part - 1) and ifpost(postArray, part, end - 1)
def ifpreorder(preArray, start, end):

	if(end - start <= 1):

		return True

	i = end

	while(i >= start and preArray[i] > preArray[start]):

		i -= 1

	partition = i

	while(i >= start and preArray[i] < preArray[start]):

		i -= 1

	if(i > start):

		return False

	return ifpreorder(preArray, start + 1, partition) and \

	 ifpreorder(preArray, partition + 1, end)

相关文章