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

Google 电面

🔗
 楼主| yzmys000 2016-7-14 06:59:20 | 只看该作者
全局:
vancexu 发表于 2016-7-13 06:45
lz能用英文解释一下“然后输出left child 跟 left child 与 right child 跟right child 与 输出结果是”是 ...

就是左子树跟左子树and 右子树跟右子树and
回复

使用道具 举报

🔗
 楼主| yzmys000 2016-7-14 07:00:00 | 只看该作者
全局:
alexanderzjs 发表于 2016-7-14 05:16
看lz给的例子应该是xor,如果是&那左边子树应该是两个0,不过这个不是重点:-)

结果写错了 是& 不好意思~
回复

使用道具 举报

🔗
muybienw 2016-7-14 08:47:28 | 只看该作者
全局:
大概写了下代码,递归做的,跑了几个简单的测试:
  1. <span style="color:#cc7832;">public </span>TreeNode <span style="color:#ffc66d;">bitAnd</span>(TreeNode a<span style="color:#cc7832;">, </span>TreeNode b) {
  2.     <span style="color:#cc7832;">if</span>(a==<span style="color:#cc7832;">null </span>&& b == <span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return null;
  3. </span><span style="color:#cc7832;">    else if</span>(a==<span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return </span>b<span style="color:#cc7832;">;
  4. </span><span style="color:#cc7832;">    else if</span>(b==<span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return </span>a<span style="color:#cc7832;">;
  5. </span><span style="color:#cc7832;">
  6. </span><span style="color:#cc7832;">    </span>TreeNode ret = <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val </span>& b.<span style="color:#9876aa;">val</span>)<span style="color:#cc7832;">;
  7. </span><span style="color:#cc7832;">    if</span>(a.<span style="color:#9876aa;">left</span>==<span style="color:#cc7832;">null </span>&& b.<span style="color:#9876aa;">left</span>==<span style="color:#cc7832;">null</span>) {
  8.         ret.<span style="color:#9876aa;">left </span>= <span style="color:#cc7832;">null;
  9. </span><span style="color:#cc7832;">    </span>}
  10.     <span style="color:#cc7832;">else</span>{
  11.         TreeNode leftA = a.<span style="color:#9876aa;">left </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val</span>) : a.<span style="color:#9876aa;">left</span><span style="color:#cc7832;">;
  12. </span><span style="color:#cc7832;">        </span>TreeNode leftB = b.<span style="color:#9876aa;">left </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(b.<span style="color:#9876aa;">val</span>) : b.<span style="color:#9876aa;">left</span><span style="color:#cc7832;">;
  13. </span><span style="color:#cc7832;">        </span>ret.<span style="color:#9876aa;">left </span>= bitAnd(leftA<span style="color:#cc7832;">, </span>leftB)<span style="color:#cc7832;">;
  14. </span><span style="color:#cc7832;">    </span>}

  15.     <span style="color:#cc7832;">if</span>(a.<span style="color:#9876aa;">right</span>==<span style="color:#cc7832;">null </span>&& b.<span style="color:#9876aa;">right</span>==<span style="color:#cc7832;">null</span>) {
  16.         ret.<span style="color:#9876aa;">right </span>= <span style="color:#cc7832;">null;
  17. </span><span style="color:#cc7832;">    </span>}
  18.     <span style="color:#cc7832;">else </span>{
  19.         TreeNode rightA = a.<span style="color:#9876aa;">right </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val</span>) : a.<span style="color:#9876aa;">right</span><span style="color:#cc7832;">;
  20. </span><span style="color:#cc7832;">        </span>TreeNode rightB = b.<span style="color:#9876aa;">right </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(b.<span style="color:#9876aa;">val</span>) : b.<span style="color:#9876aa;">right</span><span style="color:#cc7832;">;
  21. </span><span style="color:#cc7832;">        </span>ret.<span style="color:#9876aa;">right </span>= bitAnd(rightA<span style="color:#cc7832;">, </span>rightB)<span style="color:#cc7832;">;
  22. </span><span style="color:#cc7832;">    </span>}

  23.     <span style="color:#cc7832;">return </span>ret<span style="color:#cc7832;">;
  24. </span>}
复制代码
回复

使用道具 举报

🔗
muybienw 2016-7-14 08:51:54 | 只看该作者
全局:
代码贴歪了,再试一下
  1.    
  2. public TreeNode bitAnd(TreeNode a, TreeNode b) {
  3.         if(a==null && b == null) return null;
  4.         else if(a==null) return b;
  5.         else if(b==null) return a;

  6.         TreeNode ret = new TreeNode(a.val & b.val);
  7.         if(a.left==null && b.left==null) {
  8.             ret.left = null;
  9.         }
  10.         else{
  11.             TreeNode leftA = a.left == null ? new TreeNode(a.val) : a.left;
  12.             TreeNode leftB = b.left == null ? new TreeNode(b.val) : b.left;
  13.             ret.left = bitAnd(leftA, leftB);
  14.         }

  15.         if(a.right==null && b.right==null) {
  16.             ret.right = null;
  17.         }
  18.         else {
  19.             TreeNode rightA = a.right == null ? new TreeNode(a.val) : a.right;
  20.             TreeNode rightB = b.right == null ? new TreeNode(b.val) : b.right;
  21.             ret.right = bitAnd(rightA, rightB);
  22.         }

  23.         return ret;
  24.     }
复制代码
回复

使用道具 举报

🔗
hyj143 2016-7-14 08:57:24 | 只看该作者
全局:
muybienw 发表于 2016-7-14 08:51
代码贴歪了,再试一下

觉得有点 overkill 了, 因为题目说明, 中间层的Node不需要考虑 &  的
回复

使用道具 举报

🔗
hxtang 2016-7-14 09:44:22 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
readman 2016-7-14 10:16:51 | 只看该作者
全局:
这题跟旁边的那个题...剪枝天壤之别的难度....
回复

使用道具 举报

🔗
readman 2016-7-14 10:48:23 | 只看该作者
全局:
  1. public class AndTree {
  2.     public void AndTree(TreeNode t1, TreeNode t2) {
  3.         if (t1 == null && t2 == null)
  4.                 return;
  5.         if (t1.left == null && t1.right == null){
  6.             if (t1.val == 0)//0 下面的都是0
  7.                 setToZero(t2);
  8.             return;//1 下面的不用管
  9.         }
  10.         AndTree(t1.left,t2.left);
  11.         AndTree(t1.right,t2.right);
  12.     }

  13.     /**
  14.      * set leafs to zero
  15.      * @param node  root
  16.      */
  17.     public void setToZero(TreeNode node) {
  18.         if (node == null)
  19.             return;
  20.         if (node.left == null && node.right == null){
  21.             node.val = 0;
  22.             return;
  23.         }
  24.         setToZero(node.left);
  25.         setToZero(node.right);
  26.     }

  27.     public static void main(String[] args) {
  28.         TreeNode t1 = new TreeNode(-1);
  29.         t1.left = new TreeNode(0);
  30.         t1.right = new TreeNode(1);
  31.         TreeNode t2 = new TreeNode(-1);
  32.         t2.left = new TreeNode(-1);
  33.         t2.left.left = new TreeNode(1);
  34.         t2.left.right = new TreeNode(0);
  35.         t2.right = new TreeNode(-1);
  36.         t2.right.left = new TreeNode(1);
  37.         t2.right.right = new TreeNode(0);
  38.         new AndTree().AndTree(t1,t2);
  39.         System.out.println(t2);
  40.     }
  41. }
复制代码

补充内容 (2016-7-14 10:49):
就是same tree原题改的, 0的下面都是0, 需要改一下, 1 的下面不用管, 直接跳出
回复

使用道具 举报

🔗
chestnut9919 2016-7-15 04:39:53 | 只看该作者
全局:
readman 发表于 2016-7-14 10:48
补充内容 (2016-7-14 10:49):
就是same tree原题改的, 0的下面都是0, 需要改一下, 1 的下面不用管, 直接 ...

请问follow up怎么做呢?
回复

使用道具 举报

🔗
greentrail 2016-7-15 04:42:21 | 只看该作者
全局:
根据楼主的例子,题目要求是这样做and. roota (01) and rootb (1010), 注意是左对齐,结果是0010. 两个树可能高度不同。

在前面的帖子中,hyj143已经把思路说的很清楚了。
回复

使用道具 举报

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

本版积分规则

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