MediumNo. 1110
Delete Nodes And Return Forest — LeetCode 1110 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search, Array, Hash Table, Binary Tree
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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).
Example
- Input
- root = [1,2,3,4,5,6,7], to_delete = [3,5]
- Output
- [[1,2,null,4],[6],[7]]
Python solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def delNodes(
self, root: Optional[TreeNode], to_delete: List[int]
) -> List[TreeNode]:
def dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
root.left, root.right = dfs(root.left), dfs(root.right)
if root.val not in s:
return root
if root.left:
ans.append(root.left)
if root.right:
ans.append(root.right)
return None
s = set(to_delete)
ans = []
if dfs(root):
ans.append(root)
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1110. Delete Nodes And Return Forest is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0105 | Construct Binary Tree from Preorder and Inorder Traversal | Medium |
| 0106 | Construct Binary Tree from Inorder and Postorder Traversal | Medium |
| 0508 | Most Frequent Subtree Sum | Medium |
| 0652 | Find Duplicate Subtrees | Medium |
| 0653 | Two Sum IV - Input is a BST | Easy |
| 0690 | Employee Importance | Medium |
Frequently asked questions
- How hard is LeetCode 1110. Delete Nodes And Return Forest?
LeetCode 1110. Delete Nodes And Return Forest is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1110. Delete Nodes And Return Forest?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1110. Delete Nodes And Return Forest?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1110. Delete Nodes And Return Forest cover?
LeetCode 1110. Delete Nodes And Return Forest is tagged Tree, Depth-First Search, Array, Hash Table and Binary Tree on LeetCode.