687 最长同值路径（dfs）

布满荆棘的人生 2022-09-03 04:26 145阅读 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 条评论，145人围观）

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

相关阅读

相关 ( “树” 之 DFS) 687. 最长同值路径 ——【Leetcode每日一题】

687. 最长同值路径给定一个二叉树的 `root` ，返回最长的路径的长度，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。两个节点

蔚落/ 2024年03月23日 12:56/ 0 赞/ 49 阅读

相关二叉树之最长同值路径

二叉树之最长同值路径问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0

太过爱你忘了你带给我的痛/ 2023年10月06日 08:01/ 0 赞/ 38 阅读

相关 687. 最长同值路径（递归）

文章目录题目解题思路代码题目给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。

素颜马尾好姑娘i/ 2023年10月05日 17:42/ 0 赞/ 41 阅读

相关（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 赞/ 146 阅读

相关 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 阅读