狗家电面

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

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

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

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

bearicc 发表于 2017-8-14 22:33
不太了解Java。如果直接将root 设为null，不清楚其他指向这个object的对象是否也会指向null. 如果设成nul ...

typo, root -> current node

这是我的java code，用了recursion，参考的思路是leetcode 450 delete node in BST, 我大致跑了几个test case感觉好像是对的

1. public class Solution {
   
2.         public List<TreeNode> remove(TreeNode root, List<TreeNode> toRemove) {
   
3.                 List<TreeNode> prevForest = new ArrayList<>();
   
4.                 prevForest.add(root);
   
5.                 for (TreeNode r : toRemove) {
   
6.                         List<TreeNode> currForest = new ArrayList<>();
   
7.                         for (TreeNode smRoot : prevForest) {
   
8.                                 remove(smRoot, currForest, r);
   
9.                         }
   
10.                         prevForest = currForest;
    
11.                 }
    
12.                 return prevForest;
    
13.         }
    
14.         private TreeNode remove(TreeNode root, List<TreeNode> prev, TreeNode toRemove) {
    
15.                 if (root == null) {
    
16.                         return null;
    
17.                 }
    
18.                 if (root == toRemove) {
    
19.                         if (root.left != null) {
    
20.                                 prev.add(root.left);
    
21.                         }
    
22.                         if (root.right != null) {
    
23.                                 prev.add(root.right);
    
24.                         }
    
25.                         return null;
    
26.                 }
    
27.                 root.left = remove(root.left, prev, toRemove);
    
28.                 root.right = remove(root.right, prev, toRemove);
    
29.                 return root;
    
30.         }
    
31. }

复制代码

啊，14楼是错的，请大家忽略，这一版丢掉了原来的root，应该是下面的这个

1. public class Solution {
   
2.         public List<TreeNode> remove(TreeNode root, List<TreeNode> toRemove) {
   
3.                 List<TreeNode> prevForest = new ArrayList<>();
   
4.                 prevForest.add(root);
   
5.                 for (TreeNode r : toRemove) {
   
6.                         List<TreeNode> currForest = new ArrayList<>();
   
7.                         for (TreeNode smRoot : prevForest) {
   
8.                                 remove(smRoot, currForest, r);
   
9.                                 if (smRoot != r) {
   
10.                                         currForest.add(smRoot);
    
11.                                 }
    
12.                         }
    
13.                         prevForest = currForest;
    
14.                 }
    
15.                 return prevForest;
    
16.         }
    
17.         private TreeNode remove(TreeNode root, List<TreeNode> prev, TreeNode toRemove) {
    
18.                 if (root == null) {
    
19.                         return null;
    
20.                 }
    
21.                 if (root == toRemove) {
    
22.                         if (root.left != null) {
    
23.                                 prev.add(root.left);
    
24.                         }
    
25.                         if (root.right != null) {
    
26.                                 prev.add(root.right);
    
27.                         }
    
28.                         return null;
    
29.                 }
    
30.                 root.left = remove(root.left, prev, toRemove);
    
31.                 root.right = remove(root.right, prev, toRemove);
    
32.                 return root;
    
33.         }
    
34. }

复制代码

应该是下面这个

mushbunny 发表于 2017-8-15 02:15
啊，14楼是错的，请大家忽略，这一版丢掉了原来的root，应该是下面的这个
应该是下面这个

这个复杂度看起来要删掉几个node，就需要遍历几遍剩下的nodes？

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

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

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

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

我是若root本身被删除的话也留在临时结果“roots”中，最后再统一去除空nodes.

1. vector<TreeNode*> roots;
   
2. 
   
3. // helper function
   
4. void preOrderSplit(TreeNode* cur, unordered_set<TreeNode*>& toRemove) {
   
5.     if (!cur || toRemove.empty()) return;
   
6.     if (toRemove.count(cur)) {      
   
7.         if (cur->left) roots.push_back(cur->left);
   
8.         if (cur->right) roots.push_back(cur->right);
   
9.         toRemove.erase(cur); delete cur;
   
10.         return;
    
11.     }
    
12.     preOrderSplit(cur->left, toRemove);
    
13.     preOrderSplit(cur->right, toRemove);
    
14. }
    
15. 
    
16. vector<TreeNode*> split(TreeNode* r, unordered_set<TreeNode*>& toRemove) {
    
17.     roots = {r};
    
18.     for (int i = 0; i < roots.size(); ++i)
    
19.       preOrderSplit(roots[i], toRemove);
    
20.    
    
21.     vector<TreeNode*> res;
    
22.     for (auto r : roots) if (r) res.push_back(r);
    
23.     return res;
    
24. }
    

复制代码

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

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