A hanging sculpture is a binary tree. Every node is a hook with a signed number node.val (negative values are balloons that pull upward). For a hook a and a hook d strictly below it (a proper descendant), the chain from a to d is the downward path that starts at a's child on the way to d and ends at d, so it excludes a itself and includes d.
The pair (a, d) is balanced when the values on its chain add up to exactly a.val. Return the number of balanced pairs. An empty tree or a single hook has none.
Examples
5
/ \
2 5
/ / \
3 0 5
Input: root = build_tree([5, 2, 5, 3, None, 0, 5])
Output: 4
Explanation: from the root, the chains 2 -> 3, 5 and 5 -> 0 all add up to 5;
from the right child 5, the chain 5 adds up to 5.
Input: root = build_tree([0, 0, None, 0])
Output: 3
Input: root = build_tree([7])
Output: 0
Constraints
0 <= number of nodes <= 10**5-10**4 <= node.val <= 10**4- The tree may be a single chain, so its height can equal the number of nodes.
Goals
- Rewrite a path condition so both ends become a single dictionary key
- Insert a key that depends on the start node, and look up with the end node's prefix
- Count pairs along root paths without recursion on deep trees