Max Stable Path Sum in a Binary Tree
In Urban Company's service ecosystem, hierarchical data structures often represent dependencies, service categories, or operational workflows. Ensuring 'stability' in these hierarchies is crucial for reliable service delivery and resource allocation. This problem challenges you to identify and quantify the most valuable 'stable' pathways within such a system, modeled as a binary tree.
Given the root of a binary tree and an integer K, find the maximum sum of node values along any "stable" path from the root to a leaf node. A path is considered "stable" if the absolute difference between the values of any two adjacent nodes (parent and child) along that path is less than or equal to K.
Your task is to implement the maxStablePathSum function that returns this maximum sum. If no stable path exists from the root to any leaf, return -1.
Input:
root: The root node of a binary tree. Each TreeNode has an integer val, a left child, and a right child.K: An integer representing the maximum allowed absolute difference between adjacent nodes for a path to be stable.Output:
K will always be non-negative.Examples
Example 1
Input:
root = [10,5,15,3,7,null,18], K = 5
Output:
43
Note:
The stable paths from root to leaf are:
Example 2
Input:
root = [10,1,20], K = 5
Output:
-1
Note:
Paths from root to leaf:
Example 3
Input:
root = [100], K = 0
Output:
100
Note:
The tree has a single node. This path is stable by definition (no adjacent nodes to violate the condition). The sum is 100.
Constraints
N is between 1 and 10^5 (inclusive).TreeNode.val) are between -10^9 and 10^9 (inclusive).K is between 0 and 10^9 (inclusive).root will always be a valid TreeNode (i.e., not null).Loading editor...