687.Longest Univalue Path

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note:The length of path between two nodes is represented by the number of edges between them.
Method 1 DFS, O(n) time, O(1) space

• for each node, find the longest univalue path of each left and right subtree, then check if its own node's value is the same as its children.

class Solution(object):
    res = 0
    def longestUnivaluePath(self, root):
        def dfs(node):
            if not node:
                return 0 
            left = dfs(node.left)
            right = dfs(node.right)
            left_path_len, right_path_len = 0, 0
            if node.left and node.left.val == node.val:
                left_path_len += 1 + left
            if node.right and node.right.val == node.val:
                right_path_len += 1 + right
            self.res = max(self.res, left_path_len + right_path_len)
            return max(left_path_len, right_path_len)
        dfs(root)
        return self.res