Count Restricted Path Sums in Binary Tree
In a system monitoring network topology, we often analyze "paths" through connected components to understand data flow or resource dependencies. Sometimes, we're interested in paths that satisfy specific criteria, such as a cumulative value and a maximum hop count, to identify critical or bottleneck segments. This problem requires you to count such restricted paths in a hierarchical (tree-like) network representation.
You are given the root of a binary tree, an integer targetSum, and an integer maxNodes. Your task is to implement a function countRestrictedPathSums that returns the total number of paths in the tree satisfying the following conditions:
targetSum.maxNodes nodes (inclusive).countRestrictedPathSums function signature:function countRestrictedPathSums(root: TreeNode | null, targetSum: number, maxNodes: number): number
root: The root node of a binary tree. Each TreeNode has an integer val, a left child, and a right child.targetSum: An integer representing the required sum for a valid path.maxNodes: An integer representing the maximum allowed number of nodes in a valid path.root = null) should result in 0 paths.targetSum and maxNodes >= 1.targetSum can be positive, negative, or zero.Examples
Example 1
Input:
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8, maxNodes = 3
Output:
3
Note:
The tree looks like this:
10
/
5 -3
/ \
3 2 11
/ \ \
3 -2 1
Paths that sum to 8 with at most 3 nodes:
5 -> 3 (length 2, sum 8)5 -> 2 -> 1 (length 3, sum 8)-3 -> 11 (length 2, sum 8)Example 2
Input:
root = [1,2,3], targetSum = 3, maxNodes = 1
Output:
1
Note:
The tree looks like this:
1
/
2 3
Paths that sum to 3 with at most 1 node:
3 (length 1, sum 3)
The path 1 -> 2 sums to 3, but has 2 nodes, exceeding maxNodes = 1.Example 3
Input:
root = [1,2,3], targetSum = 6, maxNodes = 5
Output:
0
Note:
No path in the tree sums to 6.
Constraints
0 and 2000.Node.val is between -1000 and 1000.targetSum is between -10^9 and 10^9.maxNodes is between 1 and 2000.Loading editor...