Leetcode 687. 最长同值路径

题目描述

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

          5
         / \
        4   5
       / \   \
      1   1   5

输出:

2

示例 2:

输入:

          1
         / \
        4   5
       / \   \
      4   4   5

输出:

2

注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

解法

不妨定义findMax函数表示每个节点的最长单边路径值（所谓单边路径，即当前节点与左子树节点构成的路径，或当前节点与右子树节点构成的路径），根据某一个节点的左子节点findMax值，和右子节点findMax值，即可获得当前节点的同值路径。则遍历二叉树对每个节点的左右子节点求出findMax值，即可获得该二叉树中的最大同值路径。

class Solution(object):
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ret=0
        def findMax(root):
            if not root:
                return 0
            llen=findMax(root.left)
            rlen=findMax(root.right)
            llen=llen+1 if root.left and root.left.val==root.val else 0
            rlen=rlen+1 if root.right and root.right.val==root.val else 0
            self.ret=max(self.ret,llen+rlen)
            return max(llen,rlen)
        findMax(root)
        return self.ret