687 最长同值路径（dfs）

布满荆棘的人生 2022-09-03 04:26 144阅读 0赞

**1. 问题描述：**

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表示。

**示例 1:**

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

**示例 2:**

输入:  
1  
/ \\  
4 5  
/ \\ \\  
4 4 5  
输出:  
2  
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-univalue-path

**2. 思路分析：**

分析题目可以知道我们可以求解出每一个节点的左右子树节点数值相同的最长路径数目，声明一个全局变量来更新当前最长的路径即可。

**3. 代码如下：**

# class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        res = 0
    
        def dfs(self, root: TreeNode):
            if not root: return 0
            l = self.dfs(root.left)
            r = self.dfs(root.right)
            if not root.left or root.left.val != root.val: l = 0
            if not root.right or root.right.val != root.val: r = 0
            self.res = max(self.res, l + r)
            # 返回当前节点的节点数值相同的最大路径数目
            return max(l, r) + 1
    
        def longestUnivaluePath(self, root: TreeNode) -> int:
            self.dfs(root)
            return self.res

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关（Java）leetcode-687 Longest Univalue Path (最长同值路径)

题目描述给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表示。

╰+哭是因爲堅強的太久メ/ 2023年02月18日 08:17/ 0 赞/ 110 阅读

相关 C语言重构【687】最长同值路径

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

悠悠/ 2022年12月19日 09:20/ 0 赞/ 131 阅读

相关 leetcode687最长同值路径

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

曾经终败给现在/ 2022年09月03日 12:24/ 0 赞/ 138 阅读

相关 687 最长同值路径（dfs）

1. 问题描述：给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表示。

布满荆棘的人生/ 2022年09月03日 04:26/ 0 赞/ 145 阅读

相关 leetcode 388. Longest Absolute File Path | 388. 文件的最长绝对路径（栈+DFS）

题目 [https://leetcode.com/problems/longest-absolute-file-path/][https_leetcode.com_pro

我就是我/ 2022年08月31日 15:17/ 0 赞/ 111 阅读

相关 CSU oj 1681 Adjoin（dfs求树上最长路径）（搜索）

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1681 题目大意：给你一共有n个结点但是不连通的无向图，你需要用

拼搏现实的明天。/ 2022年08月21日 12:44/ 0 赞/ 127 阅读

相关 leetcode 687. Longest Univalue Path 二叉树最长相等路径+ 深度优先遍历DFS

Given a binary tree, find the length of the longest path where each node in the path has

刺骨的言语ヽ痛彻心扉/ 2022年06月03日 08:36/ 0 赞/ 161 阅读

相关 leetcode 687. 最长同值路径(python)

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表示。示例 1: 输

爱被打了一巴掌/ 2022年05月13日 15:58/ 0 赞/ 180 阅读

相关二叉树最长路径

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1

╰+攻爆jí腚メ/ 2022年04月15日 00:36/ 0 赞/ 221 阅读

相关 Dijksta+DFS求最短路径问题

Dijkstra+DFS Dijkstra+DFS思想 Dijkstra实现 DFS实现

你的名字/ 2021年09月21日 07:26/ 0 赞/ 356 阅读