# Delete Nodes And Return Forest

Nov 18, 2019

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:

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.

vector<TreeNode *> res;
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
if (root == nullptr) return res;

vector<bool> delmap(1001, false);
for(int i = 0;i < to_delete.size(); i++) {
delmap[to_delete[i]] = true;
}

if (!toDelNodes(root, delmap)) {
res.push_back(root);
}

return res;
}

bool toDelNodes(TreeNode *root, vector<bool>& delmap) {
if (root == nullptr) return false;

if (toDelNodes(root->left, delmap)) {
root->left = nullptr;
}
if (toDelNodes(root->right, delmap)) {
root->right = nullptr;
}

if (delmap[root->val]) {
if (root->left) res.push_back(root->left);
if (root->right) res.push_back(root->right);
return true;
}
return false;
}

LeetCodeLeetCode