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

Microsoft : Judge binary tree equality with swapping allowed

🔗
wwwyhx | 只看该作者 |倒序浏览
全局:

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

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

x
判断两二叉树全等(在可以交换左右子树的条件下),进一步给出需要多少次交换。
时间复杂度,如何优化

上一篇:Microsoft: 打印最优路径
下一篇:tsy3602 : 帖个晚上考试的算法题,如果可能的话麻烦版主重发
🔗
ziegfeld 2011-10-28 08:17:36 | 只看该作者
全局:
这题还没想出来……除了用搜索硬比。。
回复

使用道具 举报

🔗
sprime 2011-10-28 22:17:51 | 只看该作者
全局:
一亩三分地论坛提示:请勿灌水!制造没有信息量的垃圾帖子,比如谢谢楼主、收藏了,或者积分不够啊求加分等为灌水或者纯粹刷屏行为。版主会手工删除,减去你的积分。维护论坛干净,人人有责,谢谢合作!
回复

使用道具 举报

🔗
sprime 2011-10-28 22:18:07 | 只看该作者
全局:
扫一遍得到中序遍历结果,然后再逐个父节点分析
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-30 04:31:33 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-10-31 12:38 编辑

********************************************************
回复

使用道具 举报

🔗
nooneknow 2011-10-30 12:44:49 | 只看该作者
全局:
本帖最后由 nooneknow 于 2011-10-30 13:01 编辑

代码有bug吧?

贴个java的,就是繁琐点,而且得写两个函数。

public static boolean judgeEqual(TreeNode r1, TreeNode r2){
  if(r1 == null && r2 == null)
   return true;
  if(r1.data == r2.data)
   return isEqual(r1, r2);
  else
   return false;
}

public static boolean isEqual(TreeNode r1, TreeNode r2){
  //all children are null
  if(r1.left == null && r1.right == null &&
     r2.left == null && r2.right == null)
   return true;
  //all are not null
  if(r1.left != null && r1.right != null &&
     r2.left != null && r2.right != null){
   if(r1.left.data == r2.left.data && r1.right.data == r2.right.data)
    return (isEqual(r1.left, r2.left) && isEqual(r1.right, r2.right));
   if(r1.left.data == r2.right.data && r1.left.data == r2.right.data){
    cnt++;
    return (isEqual(r1.left, r2.right) && isEqual(r1.left, r2.right));
   }
  }
  //children of r1 or r2 are null
  if(r1.left == null && r1.right == null ||
     r2.left == null && r2.right == null)
   return false;
  //one child for r1 and r2
  if(r1.left == null){
   if(r2.left == null){
    if(r1.right.data != r2.right.data)
     return false;
    return isEqual(r1.right, r2.right);
   }
   else{
    if(r1.right.data != r2.left.data)
     return false;
    cnt++;
    return isEqual(r1.right, r2.left);
   }
  }
  else{
   if(r2.left != null){
    if(r1.left.data != r2.left.data)
     return false;
    return isEqual(r1.left, r2.left);
   }
   else{
    if(r1.left.data != r2.right.data)
     return false;
    cnt++;
    return isEqual(r1.left, r2.right);
   }   
  }
}
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-30 15:11:15 | 只看该作者
全局:
代码有bug吧?

贴个java的,就是繁琐点,而且得写两个函数。

public static boolean judgeEqual(TreeNode r1, TreeNode r2){
  if(r1 == null && r2 == null)
   return true;
  if(r1.data == r2.data)
   return isEqual(r1, r2);
  else
   return false;
}

public static boolean isEqual(TreeNode r1, TreeNode r2){
  //all children are null
  if(r1.left == null && r1.right == null &&
     r2.left == null && r2.right == null)
   return true;
  //all are not null
  if(r1.left != null && r1 ...
nooneknow 发表于 2011-10-30 12:44


恩, 肯定有bug, 懒得跑测试了, 麻烦, 哈哈
回复

使用道具 举报

🔗
sunstick 2011-10-31 12:05:14 | 只看该作者
全局:
  1. #define MAX_SWAP -1

  2. int swapIdentical(TreeNode* a, TreeNode* b)
  3. {
  4.   if(a && !b)
  5.     return MAX_SWAP;
  6.   if(b && !a)
  7.     return MAX_SWAP;
  8.   if(!a && !b)
  9.     return 0;

  10.   if(a -> value != b -> value)
  11.     return MAX_SWAP;
  12.   
  13.   int leftNoSwap = swapIdentical(a -> left, b -> left);
  14.   int rightNoSwap = swapIdentical(a -> right, b -> right);
  15.   
  16.   if(leftNoSwap != MAX_SWAP && rightNoSwap != MAX_SWAP)
  17.     return leftNoSwap + rightNoSwap;

  18.   int leftWithSwap = swapIdentical(a -> left, b -> right);
  19.   int rightWithSwap = swapIdentical(a -> right, b -> left);
  20.   
  21.   if(leftWithSwap != MAX_SWAP && rightWithSwap != MAX_SWAP)
  22.     return leftWithSwap + rightWithSwap + 1;
  23.   
  24.   return MAX_SWAP;
  25. }
复制代码
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-31 12:37:48 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-10-31 12:52 编辑

啊, 我的code错了, 不能判断在两个节点相等子树交换才相等的情况下, 更正:

  1. int IsEqual(NODE* p1, NODE* p2)
  2. {
  3.         if (NULL == p1 && NULL != p2)
  4.                 return -1;

  5.         if (NULL != p1 && NULL == p2)
  6.                 return -1;

  7.         if (NULL == p1 && NULL == p2)
  8.                 return 0;
  9.         if (p1->nVal != p2->nVal)                               return -1;

  10.         int nRet = -1;
  11.         int n1 = IsEqual(p1->pLft, p2->pLft);
  12.         int n2 = IsEqual(p1->pRgt, p2->pRgt);
  13.         
  14.         if (n1 >= 0 && n2 >= 0)
  15.                 return n1 + n2;

  16.         n1 = IsEqual(p1->pLft, p2->pLft);
  17.         n2 = IsEqual(p1->pRgt, p2->pRgt);

  18.         if (n1 >= 0 && n2 >= 0)
  19.                 return n1 + n2 + 1;

  20.         return -1;
  21. }
复制代码
回复

使用道具 举报

🔗
sunstick 2011-10-31 12:45:24 | 只看该作者
全局:
回复 9# wwwyhx


    23 行要返回n1 + n2 +1吧

还有,你没有判断p1,p2里面的数据是不是相同
回复

使用道具 举报

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

本版积分规则

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