Daily Leetcode 687. Longest Univalue Path

https://leetcode.com/problems/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.

The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

    5
   / \
  4   5
 / \   \
1   1   5

Output: 2

Example 2:

Input:

    1
   / \
  4   5
 / \   \
4   4   5

Output: 2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

题目分析：

这一题给的输入是一个二叉树，我们要求该二叉树中最长的相同值路径。很多与树相关的问题都可以通过递归来解决，这个问题也是如此：我们分别求左右子树中的最长相同路径长度，返回左右子树中较长的路径长度值，再判断当前结点与左右子结点的关系；若当前结点的值与左右子节点的值相同，则最长路径值+1。并且，在每一次递归时都更新当前的最大路径长度。

代码：

class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        
        def traversePath(root, rootValue):
            if not root:
                return 0;
            left, right = traversePath(root.left, root.val), traversePath(root.right, root.val)
            self.res = max(self.res, left + right)

            return 1 + max(left, right) if root.val == rootValue else 0
        
        traversePath(root, None)
        
        return self.res