diff options
author | jack <[email protected]> | 2024-07-16 20:04:41 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-07-16 20:04:41 -0600 |
commit | 0f997410755df764113d8a8a1a9a146df51c7f90 (patch) | |
tree | f3b221b3a31ec7cafb11cf06cfc11c6e64d7074d | |
parent | 213c3f676a306a98c40a23e9ab386d8551bea608 (diff) | |
download | leetcode-0f997410755df764113d8a8a1a9a146df51c7f90.tar.gz leetcode-0f997410755df764113d8a8a1a9a146df51c7f90.zip |
1110. delete nodes and return forest
-rw-r--r-- | delete_nodes_return_forest.c | 38 | ||||
-rw-r--r-- | delete_nodes_return_forest.py | 39 |
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 |