📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2420| 回复: 6
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : validate a BST

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Write a function to validate a BST

上一篇:求高手帮忙解一个投硬币的编程问题,急!!!
下一篇:Google : 找出穿过点最多的直线
🔗
 楼主| wwwyhx 2011-8-19 12:38:30 | 只看该作者
全局:

  1. struct NODE
  2. {
  3.         int nVal;
  4.         NODE* pLft;
  5.         NODE* pRgt;

  6.         NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL)
  7.         {}
  8. };

  9. bool is_bst(NODE* pRoot, int& nPrev)
  10. {
  11.         if (NULL == pRoot)
  12.                 return true;

  13.         if (!is_bst(pRoot->pLft, nPrev))
  14.                 return false;

  15.         if (pRoot->nVal >= nPrev)
  16.                 nPrev = pRoot->nVal;
  17.         else
  18.                 return false;

  19.         return is_bst(pRoot->pRgt, nPrev);
  20. }

  21. bool IsBST(NODE* pRoot)
  22. {
  23.         int dummy = 0x80000000; //smallest number
  24.         return is_bst(pRoot, dummy);
  25. }
复制代码
回复

使用道具 举报

🔗
coder 2011-8-19 23:35:10 | 只看该作者
全局:
Not my idea.

  1. public boolean is_valid(BST_Node root, int min, int max){
  2.                 if(root==null)
  3.                         return true;
  4.                 if(root.value>min && root.value<max
  5.                                 && is_valid(root.left_child, min, root.value)
  6.                                 && is_valid(root.right_child, root.value, max))
  7.                         return true;
  8.                 else
  9.                         return false;
  10.         }
复制代码
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-8-20 01:48:45 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-8-20 01:51 编辑
Not my idea.
coder 发表于 2011-8-19 23:35



    感觉不该是中序吧,这个函数怎么调用呢?
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-8-20 02:42:08 | 只看该作者
全局:

  1. bool _inner_judge(NODE* pRoot, int& nMin, int& nMax)
  2. {
  3.         if (NULL == pRoot) return true;

  4.         int nTmp1, nTmp2;
  5.         nTmp1 = pRoot->nVal;
  6.         nTmp2 = pRoot->nVal;
  7.         if (!_inner_judge(pRoot->pLft, nTmp1, nTmp2))
  8.                 return false;

  9.         if (pRoot->nVal < nTmp2)
  10.                 return false;

  11.         nMin = nTmp1;

  12.         nTmp1 = pRoot->nVal;
  13.         nTmp2 = pRoot->nVal;
  14.         if (!_inner_judge(pRoot->pRgt, nTmp1, nTmp2))
  15.                 return false;

  16.         if (pRoot->nVal > nTmp1)
  17.                 return false;

  18.         nMax = nTmp2;

  19.         return true;
  20. }

  21. bool IsBST2(NODE* pRoot)
  22. {
  23.         assert(pRoot);

  24.         int nMin, nMax;
  25.         return _inner_judge(pRoot, nMin, nMax);
  26. }
复制代码
回复

使用道具 举报

🔗
coder 2011-8-21 02:12:03 | 只看该作者
全局:
感觉不该是中序吧,这个函数怎么调用呢?
wwwyhx 发表于 2011-8-20 01:48



    调用的话,is_valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE)
不过我还没具体验证过。
回复

使用道具 举报

🔗
coder 2011-8-21 02:16:57 | 只看该作者
全局:
感觉不该是中序吧,这个函数怎么调用呢?
wwwyhx 发表于 2011-8-20 01:48




另一种方法就是中序输出,判断是否已经sorted。
....每次看帖子都要盯着版主大大的头像看一会,耽误好久....
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表