05 August 2008
给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
对某个节点的后续层递归完后在考虑删除操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode 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 {
//map存储要删的节点的值
private boolean[] map = new boolean[1001];
//ans为要输出的结果
private List<TreeNode> results = new ArrayList<>();
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
int n = to_delete.length;
for (int j : to_delete) {
map[j] = true;
}
//先看看根结点要不要删，不删的话就加进去
if (!map[root.val]) {
results.add(root);
search(root, true);
} else {
search(root, false);
}
return results;
}
//子方法输入参数的布尔值为当前节点要不要删，即是否还存在？
//当前节点是否存在决定着接下来的左右节点是否要加入结果集
public void search(TreeNode root, boolean exist) {
if (root == null) return;
//如果当前节点不存在了，且左节点不要删，就把左节点加入集合
//右节点同理
if (!exist) {
if (root.left != null && !map[root.left.val]) {
results.add(root.left);
}
if (root.right != null && !map[root.right.val]) {
results.add(root.right);
}
}
//不管当前节点还是否存在，如果左节点要删则在深入下一层时传false，表示这个节点已经不存在了
//这里的不存在并不代表已经删除，因为删除操作即断开二叉链表的操作是在递归完这个节点的后续层之后的
//这里的不存在相当于形存神灭的状态，物理上还存在，但精神上已经死亡即早晚要删先留你个躯壳
//右节点同理
if (root.left != null && map[root.left.val]) {
search(root.left, false);
root.left = null;
} else {
search(root.left, true);
}
if (root.right != null && map[root.right.val]) {
search(root.right, false);
root.right = null;
} else {
search(root.right, true);
}
}
}