Google 3.3 intern 跪经

googlerr 发表于 2016-3-8 03:05
请问下第一题返回所有 的subtree的意思是用List来返回吗？

比如原树是

如果有重复的，只返回一个就行了

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

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

googlerr 发表于 2016-3-9 00:48
只返回任意一个same subtree pair？subtree必须是到leaf吗？还是中间随便截取一段就行？如果是中间随便截 ...

必须到leaf，返回的是一组节点，以这些节点为root的subtree有重复的

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

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

googlerr 发表于 2016-3-9 04:58
OK，应该理解了。所以比如这个tree

              1

客气客气，根据我的理解，返回的应该是节点2，3，4吧，这些subtree都有重复

有人能说一下第一题的思路吗，难道是比较tree里面的每一对node作为subtree的root？

第一题求思路啊。。

kiviljc 发表于 2016-4-8 22:01
第一题求思路啊。。

1. public static boolean compare(TreeNode node1, TreeNode node2, List<Integer> ans){
   
2.                 if(node1 == null && node2 == null) return true;
   
3.                 if(node1 == null || node2 == null) return false;
   
4.                 boolean left = compare(node1.left, node2.left, ans);
   
5.                 boolean right = compare(node1.right, node2.right, ans);
   
6.                 if(node1.val == node2.val && left && right){
   
7.                         ans.add(node1.val);
   
8.                         return true;
   
9.                 }
   
10.                 return false;
    
11.         }

复制代码

我的想法。如果不对请指正。