第1页共57页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共57页第9题判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果
如果是返回true，否则返回false
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/\610/\/\57911因此返回true
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false
ANSWER:Thisisaninterestingone
Thereisatraditionalquestionthatrequiresthebinarytreetobere-constructedfrommid/post/preorderresults
Thisseemssimilar
Fortheproblemsrelatedto(binary)trees,recursionisthefirstchoice
Inthisproblem,weknowinpost-orderresults,thelastnumbershouldbetheroot
SowehaveknowntherootoftheBSTis8intheexample
Sowecansplitthearraybytheroot
intisPostorderResult(inta[],intn){returnhelper(a,0,n-1);}inthelper(inta[],ints,inte){if(e==s)return1;inti=e-1;while(a[e]>a[i]&&i>=s)i--;if(
helper(a,i+1,e-1))return0;intk=l;while(a[e]=s)i--;returnhelper(a,s,l);}第10题翻转
