Chinaunix首页 | 论坛 | 博客
  • 博客访问: 409261
  • 博文数量: 101
  • 博客积分: 2207
  • 博客等级: 大尉
  • 技术积分: 2508
  • 用 户 组: 普通用户
  • 注册时间: 2011-04-19 20:45
文章分类

全部博文(101)

文章存档

2013年(15)

2012年(86)

我的朋友

分类: C/C++

2012-09-24 22:37:24

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true,否则返回false。
例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:
8
/ /
6 10
/ / / /
5 7 9 11
因此返回true。
如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。

点击(此处)折叠或打开

  1. ool IsBstPostOrder(int *a,int low, int high)
  2. {
  3.     if (high - low > 1)
  4.     {
  5.         int root = a[high];

  6.         int left,right;
  7.         for ( left = low; left < high-1; )
  8.         {
  9.             if (a[left] < root) left++;
  10.             else break;
  11.         }

  12.         for (right = high-1; right > low; )
  13.         {
  14.             if (a[right] > root) right--;
  15.             else break;
  16.         }
  17.         if (left != right + 1) return false;

  18.         bool leftflag = IsBstPostOrder(a,low,right);
  19.         bool rightflag = IsBstPostOrder(a,left,high-1);
  20.         return leftflag && rightflag;
  21.     }
  22.     return true;
  23. }

阅读(2186) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~