第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题翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“Iamastudent.”，则输出“student.aamI”。Answer:Alreadydonethis.Skipped.第11题求二叉树中节点的最大距离...如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。ANSWER:Thisisinteresting...Alsorecursively,thelongestdistancebetweentwonodesmustbeeitherfromroottooneleaf,orbetweentwoleafs.Fortheformercase,it’sthetreeheight.Forthelattercase,itshouldbethesumoftheheightsofleftandrightsubtreesofthetwoleaves’mostleastancestor.Thefirstcaseisalsothesumtheheightsofsubtrees,justtheheight+0.intmaxDistance(Node*root){intdepth;returnhelper(root,depth);}inthelper(Node*root,int&depth){if(root==NULL){depth=0;return0;}intld,rd;intmaxleft=helper(root->left,ld);intmaxright=helper(root->right,rd);depth=max(ld,rd)+1;returnmax(maxleft,max(maxright,ld+rd));}第12题题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。ANSWER:1+..+n=n*(n+1)/2=(n^2+n)/2itiseasytogetx/2,sotheproblemistogetn^2thoughnoif/elseisallowed,wecaneasillygoaroundusingshort-pass.usingmacrotomakeitfancier:#defineT(X,Y,i)(Y&(1<>1;}第13题：题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};Answer:Twoways.1:recordthelengthofthelinkedlist,thengon-ksteps.2:usetwocursors.Timecomplexitiesareexactlythesame.Node*lastK(Node*head,intk){if(k<0)error(“k<0”);Node*p=head,*pk=head;for(;k>0;k--){if(pk->next!=NULL)pk=pk->next;elsereturnNULL;}while(pk->next!=NULL){p=p->next,pk=pk->next;}returnp;}第14题：题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。ANSWER:Usetwocursors.Oneatfrontandtheotherattheend.Keeptrackofthesumbymovingthecursors.voidfind2Number(inta[],intn,intdest){int*f=a,*e=a+n-1;intsum=*f+*e;while(sum!=dest&&f
