删点成林 图解题解

这道题到底在问什么

输入

root=[1,2,3,4,5,6,7], to_delete=[3,5]

输出

[[1,2,null,4],[6],[7]]

输入

root=[1,2,3], to_delete=[2]

输出

[[1,null,3]]

先想最直接的笨办法

80 已移除,50 的右边断开。60 和 70 现在浮了出来、不再连着任何父亲。挨个看它们,它俩的 isRoot 都是真。（动画第 17 步）

最优解：一步一步想明白

1. 3记住「被删节点的存活孩子自立成新根;靠 isRoot 标志一路往下传、谁的父亲被删谁就可能是根」,下面逐帧套它。
2. 4先看这棵树:根 50,左边 30 挂着 20 和 40,右边 80 挂着 60 和 70。要删的是 40 和 80。我们从根 50 开始一次 DFS,边走边删、边收集森林的根。
3. 5第一步,把删除集 {40, 80} 放进一个哈希集合,这样判断任意一个节点要不要删都是 O(1)。准备好就开始递归。
4. 6到根 50。根天生是「一棵树的根」,isRoot 为真。先看它在不在删除集里:50 不在,要保留。
5. 750 没被删、又是根,所以把它收进答案,它就是森林里第一棵树的根(标橙)。接着递归它的左、右孩子,因为 50 没被删,传给孩子的 isRoot 是「假」。
6. 8进到 50 的左孩子 30。它的 isRoot 是假(父亲 50 没被删,它还挂在 50 下面)。30 不在删除集里,保留。
7. 930 保留(标绿),它仍然挂在 50 的左边、不是新根。继续递归 30 的两个孩子。
8. 10进到 30 的左孩子 20。20 不在删除集里,保留。
9. 1120 保留(标绿),它是叶子,这一支到底了。回到 30,去看它的右孩子 40。
10. 12进到 30 的右孩子 40。40 在删除集里,要删掉。
11. 1340 被删除。它是叶子、没有任何孩子,所以不会产生新的森林根,只是 30 的右边这条边断开。
12. 1440 已经从树上移除,30 现在只剩左孩子 20。第一棵树这边处理完,回到根 50,去看它的右孩子 80。
13. 15进到 50 的右孩子 80。80 在删除集里,要删掉。注意 80 可不是叶子,它下面还挂着 60 和 70。
14. 1680 被删除。关键来了:80 一旦删掉,它的孩子 60 和 70 就失去了父亲。递归到它们时,传下去的 isRoot 是「真」(父亲 80 被删了),所以 60、70 只要存活,就各自成为森林里一棵新树的根。
15. 1780 已移除,50 的右边断开。60 和 70 现在浮了出来、不再连着任何父亲。挨个看它们,它俩的 isRoot 都是真。
16. 18先看 60。它的 isRoot 是真,且不在删除集里。
17. 1960 没被删、又是根,收进答案。它就是森林里第二棵树的根(标橙),这棵树只有它一个节点。
18. 20再看 70。同样 isRoot 为真、不在删除集里。
19. 2170 没被删、又是根,收进答案。它是森林里第三棵树的根(标橙),也只有它自己一个节点。
20. 22整棵树删完了,裂成了一片森林,共三棵树:第一棵是 50(左边挂 30、30 下面挂 20),第二棵是单独的 60,第三棵是单独的 70。三个橙色节点 50、60、70 就是要返回的森林根。
21. 23回头看:把删除集放进集合 O(1) 判删;一次 DFS,每到一个节点先判删,谁的父亲被删、谁自己又存活,就靠 isRoot 标志认定为新根收进答案;被删的节点返回空、让父亲断开这条边。一遍 O(n) 就把森林全收齐了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
        dead=set(to_delete); ans=[]
        def dfs(node,is_root):
            if not node: return None
            deleted=node.val in dead
            if is_root and not deleted: ans.append(node)
            node.left=dfs(node.left,deleted)
            node.right=dfs(node.right,deleted)
            return None if deleted else node
        dfs(root,True)
        return ans

#include <algorithm>
#include <functional>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: vector<TreeNode*> delNodes(TreeNode* root,vector<int>& to_delete){ unordered_set<int> dead(to_delete.begin(),to_delete.end()); vector<TreeNode*> ans; function<TreeNode*(TreeNode*,bool)> dfs=[&](TreeNode*n,bool isRoot){ if(!n)return (TreeNode*)nullptr; bool del=dead.count(n->val); if(isRoot&&!del)ans.push_back(n); n->left=dfs(n->left,del); n->right=dfs(n->right,del); return del?nullptr:n;}; dfs(root,true); return ans; }};

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public List<TreeNode> delNodes(TreeNode root,int[] to_delete){ Set<Integer> dead=new HashSet<>(); for(int x:to_delete)dead.add(x); ArrayList<TreeNode> ans=new ArrayList<>(); dfs(root,true,dead,ans); return ans;} TreeNode dfs(TreeNode n,boolean isRoot,Set<Integer> dead,List<TreeNode> ans){ if(n==null)return null; boolean del=dead.contains(n.val); if(isRoot&&!del)ans.add(n); n.left=dfs(n.left,del,dead,ans); n.right=dfs(n.right,del,dead,ans); return del?null:n;} }

复杂度

面试官可能追问