題目描述
輸入一個(gè)整數(shù)數(shù)組封豪，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果佛点。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同挂洛。
知識(shí)點(diǎn)
二叉搜索樹(shù)
Qiang的思路
想要做這道題礼预，首先需要知道什么是二叉搜索樹(shù)。
二叉搜索樹(shù)就是左子樹(shù)的所有節(jié)點(diǎn)都小于根節(jié)點(diǎn)虏劲，右子樹(shù)的所有節(jié)點(diǎn)都大于根節(jié)點(diǎn)托酸。這樣在搜索時(shí)可以二分查找。
基于二叉搜索樹(shù)的概念柒巫，很容易想到后序序列是由三部分組成的励堡。第一部分是左子樹(shù)的后序遍歷序列，第二部分是右子樹(shù)的后序遍歷序列堡掏，第三部分是根的值应结。并且第三部分只是序列的最后一個(gè)元素。
所以布疼，我們只需要根據(jù)序列的最后一個(gè)元素將除了最后一個(gè)元素的整個(gè)序列劃分為兩部分摊趾，小于的部分和大于的部分，如果劃分失敗這說(shuō)明這個(gè)序列并不是一個(gè)二叉搜索樹(shù)的后序遍歷序列游两。然后在對(duì)第一部分和第二部分通過(guò)同樣的方法去處理砾层。最終就能判斷是不是一個(gè)二叉搜索樹(shù)的后續(xù)遍歷序列了。
# -*- coding:utf-8 -*-
class Solution:
def getResult(self, sequence):
if len(sequence)<=1:
return True
m=sequence[-1]
flag=-1
for i in range(len(sequence)-1):
if flag==-1 and sequence[i]>m:
flag=i
if flag!=-1 and sequence[i]<m:
return False
return self.getResult(sequence[:i]) and self.getResult(sequence[i:-1])
def VerifySquenceOfBST(self, sequence):
# write code here
return False if len(sequence)==0 else self.getResult(sequence)
通過(guò)測(cè)試發(fā)現(xiàn)贱案，認(rèn)為空序列不是一個(gè)二叉搜索樹(shù)的后序遍歷子序列肛炮。
作者原創(chuàng)止吐，如需轉(zhuǎn)載及其他問(wèn)題請(qǐng)郵箱聯(lián)系：lwqiang_chn@163.com。
個(gè)人網(wǎng)站：https://www.myqiang.top侨糟。
