Google 11/30 onsite 面经

第一题是不是这样

public List<Node> remove(Node root) {
   List<Node> result=new ArrayList<>();
   helper(null,root,result);
   return result;
}

public void helper(Node parent,Node cur,List<Node> result) {
     if(cur==null) return;
     if(shouldRemove(cur)) {
             if(parent!=null) {
                      if(parent.left==cur) parent.left=null;
                      else parent.right=null;
             }
             helper(null,cur.left,result);
             helper(null,cur.right,result);
    } else {
             if(parent==null) result.add(cur);
             helper(cur,cur.left,result);
             helper(cur,cur.right,result);   
    }
}

补充内容 (2016-12-19 10:44):
不好意思，应该是第二题

freemail165 发表于 2016-12-19 10:43
第一题是不是这样

public List remove(Node root) {

基本上是这样吧，有个小bug

当shouldRemove(cur) return false的情况

result.add(cur) 是必须项，不需要判断parent是否为null吧

freemail165 发表于 2016-12-19 10:43
第一题是不是这样

public List remove(Node root) {

还有shouldRemove(cur) return true的case

里面应该是helper(cur,cur.left,result);
helper(cur,cur.right,result);

aangel 发表于 2016-12-19 11:21
基本上是这样吧，有个小bug

当shouldRemove(cur) return false的情况

你跟你的父节点连在一起，为什么要放到结果里
只有分开了才需要吧

aangel 发表于 2016-12-19 11:24
还有shouldRemove(cur) return true的case

里面应该是helper(cur,cur.left,result);

你自己好好考虑吧。

不是都remove了吗，还要父节点信息做什么？
对于cur.left, cur.right 他们的父节点已经是空了

freemail165 发表于 2016-12-19 11:28
你跟你的父节点连在一起，为什么要放到结果里
只有分开了才需要吧

如果shouldRemove(cur)返回false,那就表明当前节点不该被删除，要加到result的list里面

freemail165 发表于 2016-12-19 11:29
你自己好好考虑吧。

不是都remove了吗，还要父节点信息做什么？

我又看了一下题目，如果只是返回子树的根节点那这个写法就是对的

aangel 发表于 2016-12-19 12:33
我又看了一下题目，如果只是返回子树的根节点那这个写法就是对的

list是删除所有节点后原来的树分裂成的子树的集合。

根据这个描述，你觉得应该存什么呢？
只能是那些分裂后的root吧

楼主好，round 4 “然后再给你一个词，问你这一轮用这个词去猜测，是不是无用功，就是有没有必要用这个词去猜测”，啥叫再给我一个词？难道说前n-1次player1心里所想是一个词，第n次心里所想换了一个？

niulongjia 发表于 2016-12-28 08:17
楼主好，round 4 “然后再给你一个词，问你这一轮用这个词去猜测，是不是无用功，就是有没有必要用这个词去 ...

不是，这个词就是你再猜的一个词