上周G电面，还在等回复

上周电面，题目不难，边说边写code的，还没回复。
Problem:

You are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be e

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

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

补充内容 (2017-11-13 15:40):
是周二，说错了

补充内容 (2017-11-15 07:39):
几分钟前终于收到邮件告诉我过了

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

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

jason9263 发表于 2017-11-14 03:48
楼主什么解法呢?~

1. class Solution(object):
   
2.         def recCheck(self,node,fromRoot = True):
   
3.                 if shouldBeErased(node):
   
4.                         if node.left:
   
5.                                 self.recCheck(node.left)
   
6.                         if node.right:
   
7.                                 self.recCheck(node.right)
   
8.                 else:
   
9.                         if fromRoot:
   
10.                                 self.ans.append(node)
    
11.                         if node.left:
    
12.                                 self.recCheck(node.left,False)
    
13.                                 if shouldBeErased(node.left):
    
14.                                         node.left = None
    
15.                         if node.right:
    
16.                                 self.recCheck(node.right,False)
    
17.                                 if shouldBeErased(node.right):
    
18.                                         node.right = None
    
19. 
    
20.         def solution(self,root):
    
21.                 self.ans = []
    
22.                 if root:
    
23.                         self.recCheck(root)
    
24.                 return self.ans

复制代码

补充内容 (2017-11-14 10:30):
我用的Python，不知道你习惯什么语言

我想了一个BFS的做法，不知道对不对，写了一个大概的Java伪代码，大家帮我看看啊：

1. public static List<TreeNode> deleteNodes(TreeNode root) {
   
2.     List<TreeNode> res = new ArrayList<>();
   
3.     Queue<TreeNode> queue = new LinkedList<>();
   
4.     Queue<TreeNode> curLevel = new LinkedList<>();
   
5.     Map<TreeNode, TreeNode> parentmap = new HashMap<>();
   
6.     queue.offer(root);
   
7.    
   
8.     while (!queue.isEmpty()) {
   
9.       TreeNode curNode = queue.poll();
   
10.       
    
11.       
    
12.       TreeNode curParent = map.getOrDefault(curNode, null);
    
13.       if (shouldDelete(curNode)) {
    
14.         if (curParent != null) { // for parent
    
15.           curParent.left = curParent.left == curNode ? null : curParent.left;
    
16.           curParent.right = curParent.right == curNode ? null : curParent.right;
    
17.         }
    
18.         
    
19.         map.delete(curNode);
    
20.         
    
21.         if (curNode.left != null) {
    
22.           curLevel.offer(curNode.left);
    
23.           curNode.left = null;
    
24.         }
    
25.         
    
26.         if (curNode.right != null) {
    
27.           curLevel.offer(curNode.right);
    
28.           curNode.right = null;
    
29.         }
    
30.       } else {
    
31.         // node with no parent is a root
    
32.         if (curParent == null) {
    
33.           res.add(curNode);
    
34.         }
    
35.         
    
36.         parentmap.remove(curNode);
    
37.         
    
38.         if (curNode.left != null) {
    
39.           curLevel.offer(curNode.left);
    
40.           parentmap.put(curNode.left, curNode);
    
41.         }
    
42.         
    
43.         if (curNode.right != null) {
    
44.           curLevel.offer(curNode.right);
    
45.           parentmap.put(curNode.right, curNode);
    
46.         }
    
47.       }
    
48.       
    
49.       
    
50.       if (queue.isEmpty()) {
    
51.         queue = curLevel;
    
52.         curLevel = new LinkedList<>();
    
53.       }
    
54.       
    
55.     }
    
56.    
    
57.     return res;
    
58.   }

复制代码

补充内容 (2017-11-14 15:15):
第十二行手误啊，map -> parentmap

说错了。。不是上周，是周二。。

想问下楼主，erase之后它的children怎么办呢..?
谢谢楼主..！

lalasparrow 发表于 2017-11-13 16:09
想问下楼主，erase之后它的children怎么办呢..?
谢谢楼主..！

如果这个node左右两个child都有并且都不能删，那么删了这个node以后左右两个子节点各自变成另外的tree的root，所以最后会形成多个tree的forest

freegyp 发表于 2017-11-13 16:18
如果这个node左右两个child都有并且都不能删，那么删了这个node以后左右两个子节点各自变成另外的tree的r ...

好的，谢谢楼主！

楼主什么解法呢?~

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

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

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

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

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

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