I am solving a question on

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!

CodePudding user response：

Your placement of delete is correct, but since we don't know how root is allocated we can't be sure whether delete is logically correct. BTW, delete deallocates the memory but it doesn't remove the pointers themselves. You can do root->left = root->right = nullptr to take care of that. Also, have findLeaves take a reference to the pointer and set root to nullptr after the call to dfs() to fully delete the tree.