Leetcode 687. 最长同值路径

题目描述

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

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

递归

最长路径值是由一个节点的左连续边长度，加上右连续边长度之和。不妨以 path(node) 函数表示 node 节点为端点的最长连续节点个数，则遍历二叉树，找到左、右连续节点个数和的最大值即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.ret=0
        def path(node):
            if not node:
                return 0
            l=path(node.left)
            r=path(node.right)
            l=l if node.left and node.left.val==node.val else 0
            r=r if node.right and node.right.val==node.val else 0            
            self.ret=max(l+r,self.ret)
            return max(l,r)+1
        path(root)
        return self.ret

代码中以 self.ret 表示路径长度，边数相对于点数减一，所以 self.ret=l+r。