[687][简单][DFS] 最长同值路径

题目描述

687. 最长同值路径

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

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

示例 1:

输入:

              5
             / \
            4   5
           / \   \
          1   1   5
输出: 2

示例 2:

输入:

              1
             / \
            4   5
           / \   \
          4   4   5
输出: 2

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

解题思路

本题中的路径与[124][困难][DFS] 二叉树中的最大路径和中的路径是同种定义, 详情参考124题的解释.

只需要判断当前节点与左右子树根节点值是否相同, 相同则可以吸收子树根节点代表的连线长度.

# 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:
        res = float('-inf')

        def dfs(node):
            if node is None:
                return dict()

            value = node.val
            left_map = dfs(node.left)
            right_map = dfs(node.right)
            total = left_map.get(value, 0) + right_map.get(value, 0) + 1
            nonlocal res
            res = max(res, total)
            return {value: 1 + max(left_map.get(value, 0), right_map.get(value, 0))}

        dfs(root)
        return res - 1 if res != float('-inf') else 0