删点成林

记住「被删节点的存活孩子自立成新根;靠 isRoot 标志一路往下传、谁的父亲被删谁就可能是根」,下面逐帧套它。

删点成林 · 删除集 {40, 80}：先看这棵树:根 50,左边 30 挂着 20 和 40,右边 80 挂着 60 和 70。要删的是 40 和 80。我们从根 50 开始一次 DFS,边走边删、边收集森林的根。

删点成林 · 删除集 {40, 80}：第一步,把删除集 {40, 80} 放进一个哈希集合,这样判断任意一个节点要不要删都是 O(1)。准备好就开始递归。

删点成林 · 删除集 {40, 80}：到根 50。根天生是「一棵树的根」,isRoot 为真。先看它在不在删除集里:50 不在,要保留。

删点成林 · 删除集 {40, 80}：50 没被删、又是根,所以把它收进答案,它就是森林里第一棵树的根(标橙)。接着递归它的左、右孩子,因为 50 没被删,传给孩子的 isRoot 是「假」。

删点成林 · 删除集 {40, 80}：进到 50 的左孩子 30。它的 isRoot 是假(父亲 50 没被删,它还挂在 50 下面)。30 不在删除集里,保留。

删点成林 · 删除集 {40, 80}：30 保留(标绿),它仍然挂在 50 的左边、不是新根。继续递归 30 的两个孩子。

删点成林 · 删除集 {40, 80}：进到 30 的左孩子 20。20 不在删除集里,保留。

删点成林 · 删除集 {40, 80}：20 保留(标绿),它是叶子,这一支到底了。回到 30,去看它的右孩子 40。

删点成林 · 删除集 {40, 80}：进到 30 的右孩子 40。40 在删除集里,要删掉。

删点成林 · 删除集 {40, 80}：40 被删除。它是叶子、没有任何孩子,所以不会产生新的森林根,只是 30 的右边这条边断开。

删点成林 · 删除集 {40, 80}：40 已经从树上移除,30 现在只剩左孩子 20。第一棵树这边处理完,回到根 50,去看它的右孩子 80。

删点成林 · 删除集 {40, 80}：进到 50 的右孩子 80。80 在删除集里,要删掉。注意 80 可不是叶子,它下面还挂着 60 和 70。

删点成林 · 删除集 {40, 80}：80 被删除。关键来了:80 一旦删掉,它的孩子 60 和 70 就失去了父亲。递归到它们时,传下去的 isRoot 是「真」(父亲 80 被删了),所以 60、70 只要存活,就各自成为森林里一棵新树的根。

删点成林 · 删除集 {40, 80}：80 已移除,50 的右边断开。60 和 70 现在浮了出来、不再连着任何父亲。挨个看它们,它俩的 isRoot 都是真。

删点成林 · 删除集 {40, 80}：先看 60。它的 isRoot 是真,且不在删除集里。

删点成林 · 删除集 {40, 80}：60 没被删、又是根,收进答案。它就是森林里第二棵树的根(标橙),这棵树只有它一个节点。

删点成林 · 删除集 {40, 80}：再看 70。同样 isRoot 为真、不在删除集里。

删点成林 · 删除集 {40, 80}：70 没被删、又是根,收进答案。它是森林里第三棵树的根(标橙),也只有它自己一个节点。

删点成林 · 删除集 {40, 80}：整棵树删完了,裂成了一片森林,共三棵树:第一棵是 50(左边挂 30、30 下面挂 20),第二棵是单独的 60,第三棵是单独的 70。三个橙色节点 50、60、70 就是要返回的森林根。

删点成林 · 删除集 {40, 80}：回头看:把删除集放进集合 O(1) 判删;一次 DFS,每到一个节点先判删,谁的父亲被删、谁自己又存活,就靠 isRoot 标志认定为新根收进答案;被删的节点返回空、让父亲断开这条边。一遍 O(n) 就把森林全收齐了。

边界:不删则只返回原根;根被删则孩子成根;全删返回空。

两个追问:返回值重接摘除被删点;存活孩子连同其子树成新树。