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

## 题目描述

[687. 最长同值路径](https://leetcode-cn.com/problems/longest-univalue-path/)

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

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

示例 1:

```
输入:

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

示例 2:

```
输入:

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

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

## 解题思路

本题中的路径与[\[124\]\[困难\]\[DFS\] 二叉树中的最大路径和](https://kerasnoone.gitbook.io/garnet/suan-fa/shu/broken-reference)中的路径是同种定义, 详情参考124题的解释.

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

```python
# 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
```