代码之家  ›  专栏  ›  技术社区  ›  Someone

如何实际删除节点?

  •  0
  • Someone  · 技术社区  · 4 年前

    我正在解决一个问题 LeetCode.com :

    给定二叉树的根,像这样收集树的节点:
    a、 收集所有叶节点。
    b、 删除所有叶节点。
    c、 重复此操作,直到树为空。

    二是 enter image description here

    对于输入 root = [1,2,3,4,5] (上图),输出应为: [[4,5,3],[2],[1]]

    这可以归结为查找树的每个节点的高度:

    /**
     * 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;
        }
    };
    

    上述代码被接受,但这是因为OJ没有 实际检查 是否删除了节点。我的问题是,如何删除节点?具体而言:

    a、 如果我添加delete(上面的注释行),我会得到一个运行时错误;
    b、 我不能就这样 root=nullptr 像Java的人一样,由于C++在默认情况下没有垃圾收集,所以 root 节点实际上不是 已删除 (内存将继续被占用)。
    c、 我认为我们不能删除 节点位于其他任何位置。

    那我该怎么办 事实上 是否删除节点?

    谢谢

    1 回复  |  直到 4 年前
        1
  •  0
  •   David G    4 年前

    您的位置 delete 是正确的,但我们不知道怎么做 root 是否已分配我们无法确定 删去 逻辑上 对的顺便提一下 删去 释放内存,但不会删除指针本身。你可以做到 root->left = root->right = nullptr 来解决这个问题。还有,有 findLeaves 引用指针并设置 nullptr 在呼叫之后 dfs() 完全删除树。