Longest Univalue Path
MediumExtend only through equal values
Problem
Return the length of the longest path where all nodes have the same value.
At each node, extend the same-value path from each child; the longest through-node path is the answer.
The idea
Return the longest same-value path going down from each node, but only count a child's contribution when its value matches. The best path bending at a node is the sum of both qualifying sides.
The trick
- Reset a child's contribution to 0 when the values differ.
- Answer candidate = left + right; return 1 + max(left, right).
- Measured in edges.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [5,4,5,1,1,null,5] Values: 5, 4, 5, 1, 1, 5.
1dfs returns longest same-value arm2if child.val==node.val: arm=child+13best=max(best,leftArm+rightArm)Input
- array
- [5, 4, 5, 1, 1, 5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [5,4,5,1,1,null,5]
- Output:
- 2
- Explanation:
- The path of 5s has length 2 edges.
Example 2
- Input:
- tree = [1,4,5,4,4,null,5]
- Output:
- 2
- Explanation:
- The 4-4-4 path spans 2 edges.
Example 3
- Input:
- tree = [1]
- Output:
- 0
- Explanation:
- Single node → 0 edges.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.