发个Google电话面经, 求onsite

刚结束的电话面试, 感觉有点悬.

1. check two binary tree are similar

1. 
   
2.        5
   
3.    2      4
   
4. 1   3   null   6
   
5. 
   
6.       5
   
7.   2       4
   
8. 3   1  6    null
   

复制代码

即root要相等, left/right可以交换. "交换"可以进行多次.

首先想到的就是recursion遍历, 相等则继续比较, 不相等就交换着比较.[        DIS

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

不好, 估计要跪, 求onsite.




补充内容 (2016-11-29 04:20):
11月21日 已收到onsite...

finalItw 发表于 2016-11-17 13:28
哈哈 你这么一说 我当时应该坚持一下 推导出N^2的

当时脑子里想的全是明明没有空指针 你这货非说有空 ...

我感觉应该是O(2N)哎，因为最后一步是平行的，没有嵌套，只能是反正交叉遍历一次O(N)发现不Ok, 在left pair left, right pair right的正着遍历一次O(N), 楼主O(N^2)能解释一下吗？谢啦！

antonioybw 发表于 2016-11-17 11:00
感觉按照代码  应该是   T(N)=4T(N/2) + O(1)    master theory 或者换算 应该是   O（N^2）  复杂度？    ...

哈哈 你这么一说 我当时应该坚持一下 推导出N^2的

当时脑子里想的全是明明没有空指针 你这货非说有空指针

xiaozhuxiaozhu 发表于 2016-11-17 04:26
你第一题是我年初面google实习加面的原题，代码应该是对的。我当时记得time complexity是4n好像。遍历tree ...

唉 我刚发现我当时写代码 最后的return 缺了最外面的括号

当时写的时候也不是很顺  对方一直说有null pointer  解释了很久

其实到现在我也不知道自己的解法对不对...  唉, 脑子里一团浆糊.

你第一题是我年初面google实习加面的原题，代码应该是对的。我当时记得time complexity是4n好像。遍历tree有recursion也应该不会是n^2, 比如in order,pre order这些，都是o(n)吧。
我第2题是个iterator的题。

请问 为什么是

1. if(root1==null || root2==null) return true;

复制代码

而不是

1. if(root1==null && root2==null) return true;

复制代码

一个是null 一个不是，返回的就是True了呀？

novking 发表于 2016-11-17 09:34
请问 为什么是  而不是  一个是null 一个不是，返回的就是True了呀？

我也认为这里是 &&

good luck  一定onsite！

感觉按照代码  应该是   T(N)=4T(N/2) + O(1)    master theory 或者换算 应该是   O（N^2）  复杂度？   楼主过了的话来更新下吧

novking 发表于 2016-11-17 09:34
请问 为什么是  而不是  一个是null 一个不是，返回的就是True了呀？

是我的笔误  应该是 &&