# 1080. Insufficient Nodes in Root to Leaf Paths

Given the `root` of a binary tree, consider all  root to leaf paths : paths from the root to any leaf.  (A leaf is a node with no children.)

`node` is  insufficient  if every such root to leaf path intersecting this `node` has sum strictly less than `limit`.

Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

Example 1:

``````Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
``````

``````Output: [1,2,3,4,null,null,7,8,9,null,14]
``````

Example 2:

``````Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
``````

``````Output: [5,4,8,11,null,17,4,7,null,null,null,5]
``````

Example 3:

``````Input: root = [1,2,-3,-5,null,4,null], limit = -1
``````

``````Output: [1,null,-3,4]
``````

Note:

1. The given tree will have between `1` and `5000` nodes.
2. `-10^5 <= node.val <= 10^5`
3. `-10^9 <= limit <= 10^9`

``````class Solution {
public:
TreeNode* sufficientSubset(TreeNode* root, int limit) {
if (root->left == root->right) {
return root->val < limit ? nullptr : root;
}
if (root->left) {
root->left = sufficientSubset(root->left, limit - root->val);
}
if (root->right) {
root->right = sufficientSubset(root->right, limit - root->val);
}
return root->left == root->right ? nullptr : root;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1080

https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths/

https://leetcode.com/problems/insufficient-nodes-in-root-to-leaf-paths/discuss/308326/JavaC%2B%2BPython-Easy-and-Concise-Recursion

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation