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]]vertical-binary-tree-order-2
Constraints:
- The number of nodes in the given tree is at most 1000.
- Each node has a distinct value between 1 and 1000.
- to_delete.length <= 1000
- to_delete contains distinct values between 1 and 1000.
Delete Nodes from Binary Tree and Return a Forest via Recursion Algorithm
The input of the nodes are vector (list), it would be better to convert to a hashset via O(M) so that we can achieve O(1) lookup later. We define a recursive helper function that we need to pass in the parent of the root node. Then, if the root node is to be deleted, we remove the link from its parent (if there is any), and recursively check two independent sub trees (with parent is null, because the root node is removed).
Otherwise, the root (when its parent is null) should become one of the forest (pushed to the result vector), then we have to recursively check its two subtrees with parent set to root.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) { unordered_set<int> nodes; // convert to hash set for O(1) lookup later for (const auto &n: to_delete) { nodes.insert(n); } vector<TreeNode*> r; helper(root, nullptr, nodes, r); return r; } private: void helper(TreeNode* root, TreeNode* parent, unordered_set<int> &nodes, vector<TreeNode*> &result) { if (root == nullptr) return; if (nodes.count(root->val)) { // if the current node is to be deleted if (parent != nullptr) { // delete the node from its parent if (root == parent->left) { parent->left = nullptr; } else { parent->right = nullptr; } } // then we have to recursively check its both independent trees (parent is null) helper(root->left, nullptr, nodes, result); helper(root->right, nullptr, nodes, result); } else { // the root is one of the forest if (parent == nullptr) { result.push_back(root); } // check both subtrees with root as parent helper(root->left, root, nodes, result); helper(root->right, root, nodes, result); } } }; |
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
unordered_set<int> nodes;
// convert to hash set for O(1) lookup later
for (const auto &n: to_delete) {
nodes.insert(n);
}
vector<TreeNode*> r;
helper(root, nullptr, nodes, r);
return r;
}
private:
void helper(TreeNode* root, TreeNode* parent, unordered_set<int> &nodes, vector<TreeNode*> &result) {
if (root == nullptr) return;
if (nodes.count(root->val)) { // if the current node is to be deleted
if (parent != nullptr) {
// delete the node from its parent
if (root == parent->left) {
parent->left = nullptr;
} else {
parent->right = nullptr;
}
}
// then we have to recursively check its both independent trees (parent is null)
helper(root->left, nullptr, nodes, result);
helper(root->right, nullptr, nodes, result);
} else {
// the root is one of the forest
if (parent == nullptr) {
result.push_back(root);
}
// check both subtrees with root as parent
helper(root->left, root, nodes, result);
helper(root->right, root, nodes, result);
}
}
};The time complexity is O(N) where N is the number of the nodes in the binary tree as each node will be visited once. And the space complexity is also O(N) when the binary tree is degraded into a linked list and the depth (implied by the recursion), will be N.
Relevant Post: How to Delete a Node from a Binary Search Tree?
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Count the Binary Watch Stats using Bruteforce Algorithm via C++ BitSet or Compiler Intrinsics __builtin_popcount
Next Post: Facebook Onsite Interview Preparation Part 3: How to Ace a Design Interview?
