1080. Insufficient Nodes in Root to Leaf Paths
Given the root of a binary tree and an integer limit, delete all insufficient nodes in the tree simultaneously, and return the root of the resulting binary tree.
A node is insufficient if every root to leaf path intersecting this node has a sum strictly less than limit.
A leaf is a node with no children.
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]
Constraints:
- The number of nodes in the tree is in the range [1, 5000].
-
−
10
5
<
=
N
o
d
e
.
v
a
l
<
=
10
5
-10^5 <= Node.val <= 10^5
−105<=Node.val<=105 -
−
10
9
<
=
l
i
m
i
t
<
=
10
9
-10^9 <= limit <= 10^9
−109<=limit<=109
From: LeetCode Link: 1080. Insufficient Nodes in Root to Leaf Paths
Solution:
Ideas:
For each node, reduce limit by root->val. At a leaf, if the remaining path sum is still less than required, delete it.
Code:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* sufficientSubset(struct TreeNode* root, int limit) {
if (root == NULL) {
return NULL;
}
/* If this is a leaf, check root-to-leaf sum */
if (root->left == NULL && root->right == NULL) {
if (root->val < limit) {
return NULL;
}
return root;
}
/* For children, remaining required sum is limit – root->val */
root->left = sufficientSubset(root->left, limit – root->val);
root->right = sufficientSubset(root->right, limit – root->val);
/* If both children are deleted, this node becomes insufficient */
if (root->left == NULL && root->right == NULL) {
return NULL;
}
return root;
}
