力扣---1080. 根到叶路径上的不足节点-JZTXT

给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有不足节点，并返回最终二叉树的根节点。

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为不足节点，需要被删除。

叶子节点，就是没有子节点的节点。

示例 1：

输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
输出：[1,2,3,4,null,null,7,8,9,null,14]
示例 2：

输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
输出：[5,4,8,11,null,17,4,7,null,null,null,5]
示例 3：

输入：root = [1,2,-3,-5,null,4,null], limit = -1
输出：[1,null,-3,4]

提示：

树中节点数目在范围 [1, 5000] 内
-105 <= Node.val <= 105
-109 <= limit <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目是真的绕。写了三次代码再加上直接看答案才反应过来题目是要干啥。

1. 不符合要求的节点要删掉。

2. 是否符合要求是按照叶节点来判断，而不是将某个节点作为叶节点来判断。

3. 空节点直接是不符合要求。

class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (dfs(root, limit, 0)) {
            return root;
        } else {
            return null;
        }
    }
    private boolean dfs (TreeNode root, int limit, int sum) {
        if (root == null) {
            return false;
        }
        sum += root.val;
        // 遇到叶节点后，判断这条路径是否符合要求。
        if (root.left == null && root.right == null) {
            return sum >= limit;
        }
        boolean juLeft = dfs(root.left, limit, sum);
        // 如果左边的路径不符合要求，则需要删掉。
        if (!juLeft) {
            root.left = null;
        }
        boolean juRight = dfs(root.right, limit, sum);
        // 如果右边的路径不符合要求，则需要删掉。
        if (!juRight) {
            root.right = null;
        }
        // 返回包含该节点的路径是否符合要求（而不是返回以该节点为叶节点的路径是否符合要求。）
        return  juLeft || juRight;
    }
}