💯✅🔥Detailed Easy Java ,Python3 ,C++ Solution|| 1 ms ||≧◠‿◠≦✌
Intuition:\nThe given code is designed to delete nodes with values in the to_delete list from a binary tree and return the root of the resulting tree. It uses a
# Intuition:\nThe given code is designed to delete nodes with values in the `to_delete` list from a binary tree and return the root of the resulting tree. It uses a helper function to recursively traverse the tree and delete nodes. The helper function also keeps track of whether the current node is the root of the tree to decide whether to add it to the result list.\n\n---\n# Approach:\n1. Convert the `to_delete` list to a set for efficient lookups.\n2. Define a helper function `helper` that takes a node and a boolean `is_root` as arguments.\n3. In the `helper` function:\n   - If the node is `None`, return `None`.\n   - If the node\'s value is in the `to_delete` set, set `root_deleted` to `True`.\n   - If `is_root` is `True` and `root_deleted` is `False`, add the node to the result list.\n   - Recursively call `helper` on the left and right children of the current node, passing `root_deleted` as the second argument.\n   - If `root_deleted` is `True`, return `None`; otherwise, return the current node.\n4. Call the `helper` function on the root of the original tree, passing `True` as the second argument.\n5. Return the result list.\n---\n\n# Time Complexity:\nThe time complexity of this code is O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once during the traversal.\n\n---\n# Space Complexity:\nThe space complexity is O(h), where h is the height of the binary tree. This is because the recursive function call stack can grow up to the height of the tree.\n\n---\n\n# Step By Step Explanation\nLet\'s go through the code step by step using the example binary tree with the values [1, 2, 3, 4, 5, 6, 7].\n\n| Step | Description |\n| --- | --- |\n| 1 | `delNodes` method is called with `root` and `to_delete` list. |\n| 2 | `to_delete_set` is created: `{3, 5}`. |\n| 3 | `res` list is initialized as an empty list. |\n| 4 | `helper` function is called with `root` and `is_root=True`. |\n| 5-7 | `root` (1) is not in `to_delete_set`, so `root_deleted` is `False`. Since `is_root` is `True` and `root_deleted` is `False`, `root` (1) is added to `res` list. |\n| 8 | `helper` function is recursively called on left child (2) with `is_root=True`. |\n| 9-11 | `root` (2) is not in `to_delete_set`, so `root_deleted` is `False`. Since `is_root` is `True` and `root_deleted` is `False`, `root` (2) is added to `res` list. |\n| 12 | `helper` function is recursively called on left child (4) with `is_root=True`. |\n| 13-15 | `root` (4) is not in `to_delete_set`, so `root_deleted` is `False`. Since `is_root` is `True` and `root_deleted` is `False`, `root` (4) is added to `res` list. |\n| 16-19 | Left and right children of `root` (4) are `None`, so function returns `None`. |\n| 20 | `root` (4) is returned. |\n| 21 | `helper` function is recursively called on right child (5) with `is_root=True`. |\n| 22-24 | `root` (5) is in `to_delete_set`, so `root_deleted` is `True`. Since `is_root` is `True` and `root_deleted` is `True`, `root` (5) is not added to `res` list. |\n| 25-28 | Left and right children of `root` (5) are `None`, so function returns `None`. |\n| 29 | `None` is returned. |\n| 30 | `root` (2) is returned with left child (4) and right child `None`. |\n| 31 | `helper` function is recursively called on right child (3) with `is_root=True`. |\n| 32-34 | `root` (3) is in `to_delete_set`, so `root_deleted` is `True`. Since `is_root` is `True` and `root_deleted` is `True`, `root` (3) is not added to `res` list. |\n| 35-36 | `helper` function is recursively called on left child (6) and right child (7) with `is_root=False`. |\n| 37-44 | `root` (6) is not in `to_delete_set`, so `root_deleted` is `False`. Since `is_root` is `False`, `root` (6) is not added to `res` list. Left and right children of `root` (6) are `None`, so function returns `root` (6). |\n| 45-52 | `root` (7) is not in `to_delete_set`, so `root_deleted` is `False`. Since `is_root` is `False`, `root` (7) is not added to `res` list. Left and right children of `root` (7) are `None`, so function returns `root` (7). |\n| 53 | `root` (3) is returned with left child (6) and right child (7). |\n| 54 | `root` (1) is returned with left child (2) and right child (3). |\n| 55 | `delNodes` method returns `res` list containing roots of resulting trees: [1, 2, 4, 6, 7]. |\n\n---\n```java []\nclass Solution {\n        Set<Integer> to_delete_set;\n    List<TreeNode> res;\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        to_delete_set = new HashSet<>();\n        res = new ArrayList<>();\n        for (int i : to_delete)\n            to_delete_set.add(i);\n        helper(root, true);\n        return res;\n    }\n\n    private TreeNode helper(TreeNode node, boolean is_root) {\n        if (node == null) return null;\n        boolean deleted = to_delete_set.contains(node.val);\n        if (is_root && !deleted) res.add(node);\n        node.left = helper(node.left, deleted);\n        node.right =  helper(node.right, deleted);\n        return deleted ? null : node;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n        to_delete_set = set(to_delete)\n        res = []\n\n        def helper(root, is_root):\n            if not root:\n                return None\n            root_deleted = root.val in to_delete_set\n            if is_root and not root_deleted:\n                res.append(root)\n            root.left = helper(root.left, root_deleted)\n            root.right = helper(root.right, root_deleted)\n            return None if root_deleted else root\n        helper(root, True)\n        return res\n```\n```C++ []\nclass Solution {\npublic:\n    vector<TreeNode*> result;\n    set<int> to_delete_set;\n    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {\n        for (int i : to_delete)\n            to_delete_set.insert(i);\n        helper(root, result, to_delete_set, true);\n        return result;\n    }\n\n    TreeNode* helper(TreeNode* node, vector<TreeNode*>& result,\n                     set<int>& to_delete_set, bool is_root) {\n        if (node == NULL)\n            return NULL;\n        bool deleted = to_delete_set.find(node->val) != to_delete_set.end();\n        if (is_root && !deleted)\n            result.push_back(node);\n        node->left = helper(node->left, result, to_delete_set, deleted);\n        node->right = helper(node->right, result, to_delete_set, deleted);\n        return deleted ? NULL : node;\n    }\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/daaa97b0-8cbd-4e6b-ba69-37aabdc70595_1721184861.3090105.png)\n\n
['Hash Table', 'Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3']