Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1110.html
1110. Delete Nodes And Return Forest (Medium)
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
and1000
. to_delete.length <= 1000
to_delete
contains distinct values between1
and1000
.
Related Topics:
Tree, Depth-first Search
Solution 1.
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<TreeNode> delNodes(TreeNode root, int[] to_delete) { if (root == null) return new ArrayList<TreeNode>(); Set<Integer> deleteSet = new HashSet<Integer>(); for (int value : to_delete) deleteSet.add(value); List<TreeNode> nodesList = new ArrayList<TreeNode>(); Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); nodesList.add(node); TreeNode left = node.left, right = node.right; if (left != null) { map.put(left, node); queue.offer(left); } if (right != null) { map.put(right, node); queue.offer(right); } } List<TreeNode> forest = new ArrayList<TreeNode>(); if (!deleteSet.contains(root.val)) forest.add(root); for (int i = nodesList.size() - 1; i >= 0 && !deleteSet.isEmpty(); i--) { TreeNode node = nodesList.get(i); if (deleteSet.contains(node.val)) { TreeNode parent = map.get(node); if (parent != null) { if (node == parent.left) parent.left = null; else if (node == parent.right) parent.right = null; } TreeNode left = node.left, right = node.right; if (left != null) forest.add(left); if (right != null) forest.add(right); deleteSet.remove(node.val); } } return forest; } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<TreeNode> delNodes(TreeNode root, int[] to_delete) { boolean[] del = new boolean[1001]; for (int d : to_delete) { del[d] = true; } List<TreeNode> res = new ArrayList<>(); dfs(root, true, del, res); return res; } private TreeNode dfs(TreeNode root, boolean isRoot, boolean[] del, List<TreeNode> res) { if (root == null) { return null; } boolean flag = del[root.val]; if (!flag && isRoot) { res.add(root); } root.left = dfs(root.left, flag, del, res); root.right = dfs(root.right, flag, del, res); return flag ? null : root; } }
-
// OJ: https://leetcode.com/problems/delete-nodes-and-return-forest/ // Time: O(N) // Space: O(D + H) class Solution { vector<TreeNode*> ans; unordered_set<int> s; void dfs(TreeNode *root, TreeNode *p = NULL) { if (!root) return; dfs(root->left, root); dfs(root->right, root); if (s.count(root->val)) { if (p != NULL) { if (p->left == root) p->left = NULL; else p->right = NULL; } if (root->left) ans.push_back(root->left); if (root->right) ans.push_back(root->right); } else if (p == NULL) ans.push_back(root); } public: vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) { s = unordered_set<int>(begin(to_delete), end(to_delete)); dfs(root); return ans; } };
-
# 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: TreeNode, to_delete: List[int]) -> List[TreeNode]: def dfs(fa, root): if root is None: return dfs(root, root.left) dfs(root, root.right) if root.val in s: if fa and fa.left == root: fa.left = None if fa and fa.right == root: fa.right = None if root.left: ans.append(root.left) if root.right: ans.append(root.right) s = set(to_delete) ans = [] if root.val not in s: ans.append(root) dfs(None, root) return ans ############ # 1110. Delete Nodes And Return Forest # https://leetcode.com/problems/delete-nodes-and-return-forest/ # 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: TreeNode, to_delete: List[int]) -> List[TreeNode]: res = [] delete = set(to_delete) def dfs(node, is_root): if not node: return None to_delete = node.val in delete if is_root and not to_delete: res.append(node) node.left = dfs(node.left, to_delete) node.right = dfs(node.right, to_delete) return None if to_delete else node dfs(root, True) return res
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func delNodes(root *TreeNode, to_delete []int) []*TreeNode { s := map[int]bool{} for _, v := range to_delete { s[v] = true } ans := []*TreeNode{} if !s[root.Val] { ans = append(ans, root) } var fa *TreeNode var dfs func(fa, root *TreeNode) dfs = func(fa, root *TreeNode) { if root == nil { return } dfs(root, root.Left) dfs(root, root.Right) if s[root.Val] { if fa != nil && fa.Left == root { fa.Left = nil } if fa != nil && fa.Right == root { fa.Right = nil } if root.Left != nil { ans = append(ans, root.Left) } if root.Right != nil { ans = append(ans, root.Right) } } } dfs(fa, root) return ans }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function delNodes( root: TreeNode | null, to_delete: number[], ): Array<TreeNode | null> { const s: boolean[] = Array(1001).fill(false); for (const x of to_delete) { s[x] = true; } const ans: Array<TreeNode | null> = []; const dfs = (root: TreeNode | null): TreeNode | null => { if (!root) { return null; } root.left = dfs(root.left); root.right = dfs(root.right); if (!s[root.val]) { return root; } if (root.left) { ans.push(root.left); } if (root.right) { ans.push(root.right); } return null; }; if (dfs(root)) { ans.push(root); } return ans; }