In a binary tree, a walk is a path through one or more distinct nodes, where consecutive nodes are joined by an edge (it may go up to a parent and then down another branch). A walk is single-summit if, read from one end to the other, its values first strictly increase and then strictly decrease. Either part may be empty, so a single node or a strictly increasing walk also counts, but two equal neighbouring values never do.
Return the number of nodes of the longest single-summit walk, or 0 for an empty tree.
Examples
4
/ \
6 3
/ \ \
2 5 1
/
1
Input: root = build_tree([4, 6, 3, 2, 5, None, 1, 1])
Output: 6
Explanation: 1 -> 2 -> 6 -> 4 -> 3 -> 1 climbs to the summit 6, then falls.
Input: root = build_tree([1, 2, 3, 4, None, None, 5])
Output: 3
Explanation: 4 -> 2 -> 1 -> 3 -> 5 falls into a valley, so the best is 1 -> 2 -> 4 (or 1 -> 3 -> 5).
Input: root = build_tree([2, 2, 2])
Output: 1
Constraints
0 <= number of nodes <= 10**5-10**9 <= node.val <= 10**9- The tree may be a single chain, so its height can equal the number of nodes.
Goals
- Keep two downward lengths per node: strictly falling, and rising then falling
- See that the summit may lie inside one branch, so only one side may climb
- Combine the two sides at the path's highest tree node in constant time