aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjack <[email protected]>2024-07-16 20:04:41 -0600
committerjack <[email protected]>2024-07-16 20:04:41 -0600
commit0f997410755df764113d8a8a1a9a146df51c7f90 (patch)
treef3b221b3a31ec7cafb11cf06cfc11c6e64d7074d
parent213c3f676a306a98c40a23e9ab386d8551bea608 (diff)
downloadleetcode-0f997410755df764113d8a8a1a9a146df51c7f90.tar.gz
leetcode-0f997410755df764113d8a8a1a9a146df51c7f90.zip
1110. delete nodes and return forest
-rw-r--r--delete_nodes_return_forest.c38
-rw-r--r--delete_nodes_return_forest.py39
2 files changed, 77 insertions, 0 deletions
diff --git a/delete_nodes_return_forest.c b/delete_nodes_return_forest.c
new file mode 100644
index 0000000..8153ca7
--- /dev/null
+++ b/delete_nodes_return_forest.c
@@ -0,0 +1,38 @@
+// 1110. Delete Nodes And Return Forest
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+void delete_nodes(struct TreeNode **tree, struct TreeNode **res, int *res_size,
+ bool *del) {
+ if (!*tree)
+ return;
+ delete_nodes(&(*tree)->left, res, res_size, del);
+ delete_nodes(&(*tree)->right, res, res_size, del);
+ if (!del[(*tree)->val])
+ return;
+ if ((*tree)->left)
+ res[(*res_size)++] = (*tree)->left;
+ if ((*tree)->right)
+ res[(*res_size)++] = (*tree)->right;
+ *tree = NULL;
+}
+
+struct TreeNode **delNodes(struct TreeNode *root, int *to_delete,
+ int to_deleteSize, int *returnSize) {
+ *returnSize = 0;
+ struct TreeNode **ans =
+ (struct TreeNode **)calloc(1001, sizeof(struct TreeNode *));
+ bool *del = (bool *)calloc(1001, sizeof(bool));
+ for (int i = 0; i < to_deleteSize; i++)
+ del[to_delete[i]] = true;
+ delete_nodes(&root, ans, returnSize, del);
+ if (root)
+ ans[(*returnSize)++] = root;
+ return ans;
+}
diff --git a/delete_nodes_return_forest.py b/delete_nodes_return_forest.py
new file mode 100644
index 0000000..d9a95ad
--- /dev/null
+++ b/delete_nodes_return_forest.py
@@ -0,0 +1,39 @@
+# 1110. Delete Nodes And Return Forest
+
+"""
+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.
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def delNodes(self, root, to_delete):
+ """
+ :type root: TreeNode
+ :type to_delete: List[int]
+ :rtype: List[TreeNode]
+ """
+ sel_del, ans = set(to_delete), []
+
+ def helper(root, is_root):
+ if not root:
+ return None
+ root_del = root.val in sel_del
+ if is_root and not root_del:
+ ans.append(root)
+ root.left = helper(root.left, root_del)
+ root.right = helper(root.right, root_del)
+ return None if root_del else root
+
+ helper(root, True)
+ return ans