LC-0687 Medium LeetCode

687. Longest Univalue Path

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 43% Topics: Tree, Depth-First Search, Binary Tree

Reading material

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(h)

class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        result = [0]
        def dfs(node):
            if not node:
                return 0
            left, right = dfs(node.left), dfs(node.right)
            left = (left+1) if node.left and node.left.val == node.val else 0
            right = (right+1) if node.right and node.right.val == node.val else 0
            result[0] = max(result[0], left+right)
            return max(left, right)

        dfs(root)
        return result[0]

Solution from kamyu104/LeetCode-Solutions · MIT