# LeetCode: 1080. 根到叶路径上的不足节点¶

## 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]


输入：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]


输入：root = [5,-6,-6], limit = 0



• 给定的树有 1 到 5000 个节点
• -10^5 <= node.val <= 10^5
• -10^9 <= limit <= 10^9

## 2、解题思路¶

• 一遍深度优先搜索

• 由于是路径上面的和值，需要同时向下传递当前路径的值才能判断子路径是否需要删除

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:

def dfs(node: TreeNode, father_sums):
if not node:
return 0

left = dfs(node.left, father_sums + node.val)
right = dfs(node.right, father_sums + node.val)

sub_sum = 0
if node.left and node.right:
sub_sum = max(left, right)
elif node.left:
sub_sum = left
elif node.right:
sub_sum = right

if father_sums + node.val + left < limit:
node.left = None
if father_sums + node.val + right < limit:
node.right = None

return node.val + sub_sum