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

Amazon: Build a binary tree according to "N", "L" format

全局:

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

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

x
There is binary tree with special property that all its inner node have val = 'N' and all leaves have val = 'L', every node either have two children or no child.
Given its preorder. construct the tree and return the root node

这题如果没有限制不能只有一个child的话就是NPC了,仔细想想...

上一篇:Amazon: Determine palindrome link
下一篇:问一个c语言语法问题....
🔗
 楼主| wwwyhx 2011-7-15 15:53:34 | 只看该作者
全局:
有点像之前那个facebook计算器那题,既然规定了不能只有一个孩子的情况,那么语法结构就是固定的,也就是说一个合法的表达式只能推导出一个合法的结构:
EXP={L | N(EXP EXP)}

递归下降解析函数如下

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

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

  9. NODE* Parse(char*& p)
  10. {
  11.         if (NULL == p)
  12.                 return NULL;

  13.         NODE* pRet = NULL;
  14.         if ('N' == *p)
  15.         {
  16.                 p++;
  17.                 pRet = new NODE('N');
  18.                 pRet->pLft = Parse(p);
  19.                 pRet->pRgt = Parse(p);
  20.         }
  21.         else if ('L' == *p)
  22.         {
  23.                 p++;
  24.                 pRet = new NODE('L');
  25.         }
  26.         else
  27.                 cout<<"error, unknown character found"<<endl;

  28.         return pRet;
  29. }
复制代码
回复

使用道具 举报

🔗
chriscxd 2012-8-5 09:53:23 | 只看该作者
全局:
不是故意挖坟,觉得这个题挺有意思的,以下是我的想法:

既然给定了前序遍历,第一个元素肯定是root,剩下的问题就是怎么把第二个元素开始的后缀子串划分成左右两部分,左面是所有左子树的元素,右面是所有右子树的元素。只要找到这个,用递归来建树就非常直观了。

题目给定每个node只能有0个或2个children,就此判断任何合法的子树中L点的数量一定比N点多一个,也就是numberOf(leave node)= numberOf(inner node) + 1。 这一点只要想象一下树是怎么建起来的,用数学归纳法做一遍就明白了。有了这个性质,我们可以把这个后缀子串扫描一遍,维护一个见到过的N点的数量和一个见到过的L点的数量,当扫到某一个位置发现L点数量比N点正好多一个的时候,我们就正好已经找到左子树的所有元素,剩下的就是递归的去建两个子树,然后和原先的第一个元素合并成答案.

粗略想了下觉得应该是这样的,但要完全证明正确性恐怕要写很长。大家可以探讨一下是不是正确.
回复

使用道具 举报

🔗
BinaryWitch 2012-8-5 14:14:37 | 只看该作者
全局:
本帖最后由 BinaryWitch 于 2012-8-5 14:42 编辑
chriscxd 发表于 2012-8-5 09:53
不是故意挖坟,觉得这个题挺有意思的,以下是我的想法:

既然给定了前序遍历,第一个元素肯定是root,剩 ...

同意 就用你说的那个叶子数比度为2的结点数多1就可以证明吧 划分后剩下的交给归纳

回复

使用道具 举报

🔗
wecing 2012-8-7 16:58:42 | 只看该作者
全局:
不用那么麻烦吧。如果给出的是前序遍历又是完全二叉树的话,只要:
1. 第一个N:root
2. 以后每次遇到N:当前节点的左儿子,如果当前节点已经有左儿子的话就是当前节点的右儿子。
3. 遇到L:当前节点的左儿子,如果当前节点已经有左儿子的话就是当前节点的右儿子,然后开始上升,直到当前节点没有右儿子为止。

时间复杂度为O(N),其中N为输入数据的长度(也就是‘N’和‘L’个数的总和)。
回复

使用道具 举报

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

本版积分规则

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