458. Longest Univalue Path
You are given the root of a binary tree. Return the length of the longest path on which every node carries the same value.
A path here is any chain of nodes connected by parent–child edges that never revisits a node — it does not have to pass through the root, and it is allowed to bend once (go down one child, back up through a node, and down the other child). Length is measured in edges, so a lone node is a path of length 0 and an empty tree answers 0.
Example 1:
Input: root = [5, 4, 5, 1, 1, null, 5]
Output: 2
Explanation: The chain of 5s down the right side (root 5 → right child 5 → its right child 5) uses 2 edges. No same-value path is longer.
Example 2:
Input: root = [1, 4, 5, 4, 4, null, 5]
Output: 2
Explanation: The best path bends at the left 4: leaf 4 → 4 → leaf 4, which is 2 edges. The two 5s on the right only manage 1 edge.
Constraints:
- 0 ≤ number of nodes ≤ 10⁴
- -1000 ≤ Node.val ≤ 1000
- The depth of the tree does not exceed 1000.
Hints:
Any same-value path has a unique highest node. Seen from that node, the path is just two independent straight 'arms': one running down the left side and one down the right, all carrying the node's value.
Write a post-order DFS that returns the longest single arm hanging below a node. While unwinding, an arm from a child only extends to the parent when the child's value matches the parent's; the sum of the (possibly extended) left and right arms is a candidate answer at that node.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 4, 5, 1, 1, null, 5]
Expected output: 2