'How do I actually delete the node(s)?
I am solving a question on LeetCode.com:
Given the root of a binary tree, collect a tree's nodes as if you were doing this:
a. Collect all the leaf nodes.
b. Remove all the leaf nodes.
c. Repeat until the tree is empty.
For the input
root = [1,2,3,4,5](image above), the output should be:[[4,5,3],[2],[1]].
This comes down to finding the height of each node of the tree:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> m;
int dfs(TreeNode* root) {
if(!root) return -1;
int l=dfs(root->left);
int r=dfs(root->right);
int height=max(l,r)+1;
if(height==m.size()) m.push_back({});
m[height].push_back(root->val);
//delete root;
return height;
}
vector<vector<int>> findLeaves(TreeNode* root) {
dfs(root);
return m;
}
};
The above code gets accepted, but that is because the OJ does not actually check if the nodes were deleted or not. My question is, how do I delete the nodes? Specifically:
a. If I add delete (commented line above), I get a runtime error;
b. I cannot just set root=nullptr like the Java folks, since C++ does not have garbage collection by default and so the root node would not really be deleted (the memory would continue to be occupied).
c. I don't think we can delete the root node anywhere else.
So how do I go about actually deleting the node?
Thanks!
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|

