【剑指Offer面试题】九度OJ1367：二叉搜索树的后序遍历序列

分类：剑指OFFER

题目链接地址： ?pid=1367

题目1367：二叉搜索树的后序遍历序列

时间限制：1 秒内存限制：32 兆特殊判题：否提交：1616解决：796 题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。输入：每个测试案例包括2行：第一行为1个整数n(1<=n<=10000)，，表示数组的长度。第二行包含n个整数，表示这个数组，数组中的数的范围是[0,100000000]。输出：对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结果输出Yes，否则输出No。样例输入： 7 5 7 6 9 11 10 8 4 7 4 6 5 样例输出： Yes No

思路分析：抓住题目的特点：二叉搜索树：二叉搜索树的左子树中的所有元素均小于根结点的值,右子树中的所有元素均大于根结点的值. 后序遍历:最后一个元素对应根节点. 所以在数组中小于根节点大于根节点根节点。这样可以递归往下检查所有子树，全部符合的话，说明能够造出一个二叉搜索树。时间复杂度O(nlogn) 空间复杂度O(1)

代码：

/********************************* 【剑指Offer面试题】九度OJ1367：二叉搜索树的后序遍历序列Author:牧之丶 Date：2015年Email:bzhou84@163.com **********************************/; bool VerifySequenceBST(int *sequence,int len){if(sequence==NULL || len<1)return false;int root = sequence[len-1];int i;for(i=0;i<len-1;i++)if(sequence[i]>root)break;int j = i;for(;j<len-1;j++)if(sequence[j]<root)return false;bool left = true;if(i > 0)left = VerifySequenceBST(sequence,i);bool right = true;if(i < len-1)right = VerifySequenceBST(sequence+i,len-i-1);return (left && right);}int main(){int n;while(scanf(“%d”,&n) != EOF){int *sequence = (int *)malloc(n*sizeof(int));if(sequence == NULL)exit(EXIT_FAILURE);int i;for(i=0;i<n;i++)scanf(“%d”,sequence+i);if(VerifySequenceBST(sequence,n))printf(“Yes\n”);elseprintf(“No\n”);}return 0;}/**************************************************************Problem: 1367Language: C++Result: AcceptedTime:10 msMemory:1020 kb****************************************************************

上一篇【剑指Offer面试题】九度OJ1523：从上往下打印二叉树下一篇【剑指Offer面试题】九度OJ1368：二叉树中和为某一值的路径

顶1踩0

相关文章：

你感兴趣的文章：

标签云：