📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : 根据前续遍历和中序遍历构建二叉树

🔗
pollyed 2012-11-4 17:01:49 | 只看该作者
全局:
本帖最后由 pollyed 于 2012-11-4 17:03 编辑

编程之美上有这道题,但是解法和代码不够简洁。
一个更简洁的方法:

/*
使用递归的思想,ipos指向中序遍历序列()a[],ppos指向先序遍历序列a()[],
其中()的长度为k, rpos执行完for循环应该指向a,这里根节点是a,如此递归即可处理所有节点。
这里预处理应该把每个节点处理成不一样的表示方式。
*/
  1. BinTree node( char *ppos, char *ipos, int n )
  2. {
  3.         if( n <= 0 ) return NULL;
  4.         ptr -> info = *ppos;
  5.         for( rpos = ipos ; rpos < ipos + n ; rpos ++)
  6.                 if( *rpos == *ppos ) break ;
  7.         k = rpos - ipos ;
  8.         ptr -> llink = node( ppos + 1 , ipos , k );
  9.         ptr -> rlink = node( ppos + 1 + k , rpos + 1, n - 1 - k);
  10.         return ptr ;
  11. }
复制代码




回复

使用道具 举报

🔗
nooneknow 2012-11-5 05:47:41 | 只看该作者
全局:
pollyed 发表于 2012-11-4 17:01
编程之美上有这道题,但是解法和代码不够简洁。
一个更简洁的方法:

+1

这个用递归,实在是太elegant了。
回复

使用道具 举报

🔗
pollyed 2012-11-5 11:45:26 | 只看该作者
全局:
nooneknow 发表于 2012-11-5 05:47
+1

这个用递归,实在是太elegant了。

保存好状态,就可以消除递归了。

亲,给一粒大米把,不小心变成了99积分,有些帖子看不了了
回复

使用道具 举报

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

本版积分规则

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