题目大意：
根到叶路径上的不足节点
给定一棵二叉树的根 root，请你考虑它所有 从根到叶的路径：从根到任何叶的路径。（所谓一个叶子节点，就是一个没有子节点的节点）
假如通过节点 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 = [5,-6,-6], limit = 0 输出：[]
提示：
- 给定的树有
1到5000个节点 -10^5 <= node.val <= 10^5-10^9 <= limit <= 10^9
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1080
解题思路分析：
这是一道二叉树的题目，LEETCODE中此类题目不在少数。需要遍历所有路径时，应下意识想到递归或者说是dfs搜索。本题也应该使用到递归方式来解题。
题目要求求出所有根节点到所有叶子节点的路径，每条路径上的节点和不能小于limit。如果通过某一个节点的所有路径的和都小于limit，那么这个节点应该被删除。我们需要遍历每一条路径，查看root到叶子间的和是否满足条件。进而对于任意一个节点，如果它左右两条分支下的所有路径均不符合条件，就应该删除当前节点。
我们利用递归函数先遍历到每个叶子节点，递归函数的参数中需要传入一个当前的节点和，到叶子节点时，如果这个和小于limit，说明该路径是非法路径，由于叶子节点只存在当前这唯一的路径，因此该叶子节点应当被删除，返回null，反之则应该被保留，将当前节点返回到递归上层函数。
对于非叶子节点，我们可以利用递归函数分别得到左右两个子节点，如果两个节点均为空，说明左右两条路径均为非法路径，当前节点应当被删除，返回null给上层递归函数，反之则说明存在合法路径，可将当前节点返回给上层递归函数。直到回溯到root，递归结束，root即是最终答案。
看下完整代码。
public TreeNode sufficientSubset(TreeNode root, int limit) {
return help(root, limit, 0);
}
TreeNode help(TreeNode root, int limit, int sum){
if(root == null){ // 当前节点为空，返回空
return null;
}
if(root.right==null && root.left==null){ // 叶子节点
return sum + root.val < limit ? null : root; // 判断该路径和是否合法，非法时返回空
}
// 非叶子节点
TreeNode left = help(root.left, limit, sum + root.val); // 递归得到左节点
TreeNode right = help(root.right, limit, sum + root.val); // 递归得到右节点
root.left=left;
root.right=right;
if(left==right){ // 左右节点均为空，说明无合法路径，返回空
return null;
}else{
return root; // 存在合法路径，返回当前节点
}
} 本解法用时1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Insufficient Nodes in Root to Leaf Paths.
Memory Usage: 38.5 MB, less than 100.00% of Java online submissions for Insufficient Nodes in Root to Leaf Paths.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1080-insufficient-nodes-in-root-to-leaf-paths-解题思路分析/