Description
Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
Example
1
2
| Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]
|
Constraints:
- The number of nodes in the given tree is at most 1000.
- Each node has a distinct value between 1 and 1000.
- to_delete.length <= 1000
- to_delete contains distinct values between 1 and 1000.
Solution
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
|
class Solution {
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
HashSet<Integer> set = new HashSet<>();
for (int num: to_delete)
set.add(num);
List<TreeNode> res = new ArrayList<TreeNode>();
helper(root, res, set, true);
return res;
}
public TreeNode helper(TreeNode node, List<TreeNode> res, HashSet<Integer> set, boolean isRoot){
if (node == null) return null;
boolean isDeleted = set.contains(node.val);
if (isRoot && !isDeleted) res.add(node);
node.left = helper(node.left, res, set, isDeleted);
node.right = helper(node.right, res, set, isDeleted);
return isDeleted ? null : node;
}
}
|