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
1
/ \
2 3
/ \ / \
4 -99 -99 7
/ \ / \ / \ / \
8 9 -99 -99 12 13 -99 14
---
1
/ \
2 3
/ \
4 7
/ \ \
8 9 14Input
root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1Output
[1,2,3,4,null,null,7,8,9,null,14]After deleting all nodes that are only on root-to-leaf paths with sums less than 1, the remaining tree is represented by the output.
Example 2
5 5
/ \ / \
4 8 4 8
/ / \ / / \
11 17 4 -> 11 17 4
/ \ / \ / /
7 1 5 3 7 5Input
root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22Output
[5,4,8,11,null,17,4,7,null,null,null,5]Nodes such as the leaf with value 1 are removed because every root-to-leaf path through them has sum less than 22.
Constraints
- The number of nodes in the tree is in the range
[1, 5000]. -10^5 <= Node.val <= 10^5-10^9 <= limit <= 10^9