力扣刷题记录： 1080. 根到叶路径上的不足节点

        本题是第 140 场周赛的 Q3，LC竞赛分为 1806。主要考察递归。我觉得这道题不值这个分。

方法一. 递归

        我们将通过一个节点的“根-叶”路径分解为两部分，一部分为根到其父节点，另一部分为它到叶子节点。前一部分的 val 值之和是固定的，可以在递归中使用一个变量 pre 来记录。后一部分，只需要看从它到叶子节点的路径上值之和最大的那条路径即可（参考value()函数），如果最大的路径都无法大于 limit，其他路径肯定也不行，那就删除节点。删除节点通过修改 parent 之中相应指针的指向即可。

        注意需要对 root 进行特殊判定。

        代码如下：

class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {

        if(value(root)<limit) return nullptr;
        
        delete_node(root->val,root->left,root,limit);
        delete_node(root->val,root->right,root,limit);
        return root;
    }

    void delete_node(int pre,TreeNode* now,TreeNode* parent,int limit){
        if(now==NULL) return;
        
        if(parent->left==now && pre+value(now)<limit){
            parent->left = NULL;
            return;    
        }

        if(parent->right==now && pre+value(now)<limit){
            parent->right = NULL;
            return;
        }

        delete_node(pre+now->val,now->left,now,limit);
        delete_node(pre+now->val,now->right,now,limit);
        
    }

    int value(TreeNode* root){
        if(root==NULL) return 0;

        if(!root->left&&!root->right) return root->val;
        if(!root->left) return root->val+value(root->right);
        if(!root->right) return root->val+value(root->left); 

        int a = value(root->left);
        int b = value(root->right);
        return root->val+max(a,b);
    }
};

        这道题如果改成把不足节点删掉之后，自动让其左子节点/右子节点替代其位置，而不是子节点随着不足节点一起删除，可能还要麻烦一些。