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
1and1000. to_delete.length <= 1000to_deletecontains distinct values between1and1000.
Solution: Recursion / Post-order traversal
Recursively delete nodes on left subtree and right subtree and return the trimmed tree.
if the current node needs to be deleted, then its non-null children will be added to output array.
Time complexity: O(n)
Space complexity: O(|d| + h)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) { vector<TreeNode*> ans; unordered_set<int> s{begin(to_delete), end(to_delete)}; function<TreeNode*(TreeNode*)> del = [&](TreeNode* n) -> TreeNode* { if (!n) return nullptr; if (n->left) n->left = del(n->left); if (n->right) n->right = del(n->right); if (!s.count(n->val)) return n; if (n->left) ans.push_back(n->left); if (n->right) ans.push_back(n->right); return nullptr; }; TreeNode* r = del(root); if (r) ans.push_back(r); return ans; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Author: Huahua class Solution: def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]: ans = [] ds = set(to_delete) def process(n): if not n: return None n.left, n.right = process(n.left), process(n.right) if n.val not in ds: return n if n.left: ans.append(n.left) if n.right: ans.append(n.right) return None root = process(root) if root: ans.append(root) return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment