上周G电面，还在等回复

我想了一个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

还有就是，这个数是BST的话会容易做吗？应该一样吧？

Urumic 发表于 2017-11-14 12:22
我想了一个BFS的做法，不知道对不对，写了一个大概的Java伪代码，大家帮我看看啊：

第12行是不是"parentmap.getOrDefault(curNode, null);"?

BST的话你看我楼上的回复有没有问题

您好！
本帖隐藏的内容需要积分高于 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

wojiushieyu 发表于 2017-11-28 23:44
public List erase(Node root) {
                List res = new LinkedList();
                helper(root, res, true);

thanks for your code

LUOLUOLNSH 发表于 2017-12-1 23:20
thanks for your code

不客气 感觉这种non tail recursion 能不能现场想出来写出来全看心情.....手动滑稽

感谢分享！ 楼主好运！

多谢楼主分享～～～～～

freegyp 发表于 2017-11-14 11:41
你是说第二个followup吗？我当时说的意思大概是我觉得就算是BST，还是没有办法比这个好，除非这两种情况
...

求问楼主，如果按preorder排好了有什么好处么？如果是BST的话，我们找每个要删除的node难道不是用大小关系么？