Leetcode 1110: Delete Nodes And Return Forest
Given the root of a binary tree, and a list of values to delete, your task is to remove the nodes with the given values. The resulting tree will become a forest, where each tree is a disjoint set of nodes. Return the roots of the trees in the remaining forest.
Problem
Approach
Steps
Complexity
Input: You are given the root of a binary tree and a list `to_delete` containing the values of the nodes to be removed. The tree is a binary tree with distinct node values.
Example: Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Constraints:
• The number of nodes in the tree is at most 1000.
• Each node has a distinct value between 1 and 1000.
• The `to_delete` array contains distinct values between 1 and 1000.
Output: Return a list of trees in the forest (represented by their roots). The trees are in the remaining forest after deleting the specified nodes.
Example: Output: [[1,2,null,4],[6],[7]]
Constraints:
• The result should be the list of roots of the disjoint trees formed after deletion.
Goal: The goal is to remove nodes from the tree and form multiple disjoint trees. These disjoint trees should be collected and returned as a list of roots.
Steps:
• Create a set from the `to_delete` list for efficient lookups.
• Traverse the tree and delete the nodes found in `to_delete`.
• For each node that is a root of a new tree, add it to the result list.
• During traversal, ensure that after deletion, the children of deleted nodes are properly handled as roots of new trees.
Goal: The solution should handle the upper limits of input sizes efficiently.
Steps:
• The tree is guaranteed to have at most 1000 nodes.
• The `to_delete` array will contain distinct integers within the range of node values.
Assumptions:
• Nodes to be deleted will always exist in the tree.
• After deletion, the remaining trees are disjoint and valid.
• Input: Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
• Explanation: In this example, the nodes with values 3 and 5 will be removed from the tree. This results in three disjoint trees: one with root 1, another with root 6, and another with root 7.
• Input: Input: root = [1,2,4,null,3], to_delete = [3]
• Explanation: Here, node 3 is deleted, and the resulting tree will have a single tree rooted at 1 with child 2 and 4.
Approach: To solve this problem, we use a recursive depth-first traversal. During the traversal, we will delete the specified nodes and reassign the children of deleted nodes to be roots of new trees if necessary.
Observations:
• We need to traverse the tree and check if the current node is in the `to_delete` list. If it is, we remove it and its children become new trees.
• A depth-first search (DFS) approach can be used to handle the tree traversal and deletion of nodes efficiently.
Steps:
• Create a set `to_del` from the `to_delete` array for fast lookups.
• Implement a recursive DFS function that processes each node. If the node is to be deleted, make its children the roots of new trees.
• For each node that is not deleted, recursively process its left and right children.
• If the node is a root (not deleted), add it to the result list.
Empty Inputs:
• If the input tree is empty, the result should also be empty.
Large Inputs:
• The solution should efficiently handle trees with up to 1000 nodes.
Special Values:
• If the tree contains only the nodes that are to be deleted, the result should be an empty list.
Constraints:
• The solution should process the tree in O(n) time where n is the number of nodes in the tree.
class Solution {
vector<TreeNode*> ans;
set<int> to_del;
public:
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
for(int i: to_delete) to_del.insert(i);
helper(root, true);
return ans;
}
TreeNode* helper(TreeNode* root, bool is_root) {
if(root == NULL) return NULL;
bool del = to_del.find(root->val) != to_del.end();
if(is_root && !del) ans.push_back(root);
root->left = helper(root->left, del);
root->right = helper(root->right, del);
return del? NULL : root;
}
1 : Class Declaration
class Solution {
The class `Solution` is defined, which contains methods for solving the problem of deleting nodes from a binary tree.
2 : Variable Declaration
vector<TreeNode*> ans;
A vector `ans` is declared to store the remaining nodes in the tree after the specified nodes are deleted.
3 : Variable Declaration
set<int> to_del;
A set `to_del` is declared to hold the values of the nodes that need to be deleted, ensuring efficient look-up times.
4 : Access Modifier
public:
The `public` access modifier is used to expose the methods of the class to be accessible from outside the class.
5 : Function Declaration
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
The method `delNodes` is declared, which accepts the root of the binary tree and a list of node values to delete. It returns a vector containing the remaining trees after deletions.
6 : Inserting to Set
for(int i: to_delete) to_del.insert(i);
A loop iterates through the list `to_delete`, inserting each node value into the `to_del` set, marking the nodes that need to be deleted.
7 : Recursive Call
helper(root, true);
The helper function is called with the root node and a `true` flag, indicating that the root of the tree is initially considered a potential root of a new tree after deletion.
8 : Return Statement
return ans;
The method returns the `ans` vector, which contains the roots of the remaining trees after the deletions have been processed.
9 : Function Declaration
TreeNode* helper(TreeNode* root, bool is_root) {
The helper function is declared. It takes a node `root` and a boolean `is_root` to determine if the current node is the root of a new tree.
10 : Base Case
if(root == NULL) return NULL;
The base case of the recursion checks if the current node is `NULL`. If it is, the function returns `NULL` to stop further recursion.
11 : Node Deletion Check
bool del = to_del.find(root->val) != to_del.end();
A boolean variable `del` is set to `true` if the current node's value is in the `to_del` set, indicating that the node should be deleted.
12 : Adding Root to Result
if(is_root && !del) ans.push_back(root);
If the current node is a root and not marked for deletion, it is added to the `ans` vector, representing a new tree root.
13 : Recursive Call for Left Child
root->left = helper(root->left, del);
The helper function is called recursively for the left child of the current node. The `del` flag is passed to indicate whether the node should be deleted.
14 : Recursive Call for Right Child
root->right = helper(root->right, del);
The helper function is called recursively for the right child of the current node with the `del` flag.
15 : Return Statement
return del? NULL : root;
If the current node is marked for deletion, `NULL` is returned to remove it; otherwise, the current node is returned to link the tree structure.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) where n is the number of nodes in the tree. We traverse the tree once, visiting each node.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the recursive stack and the storage of the result list, where n is the number of nodes.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus