Java实现 LeetCode 687 最长同值路径（递归）

痛定思痛。 2023-07-22 09:28 6阅读 0赞

## 687. 最长同值路径 ##

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

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

示例 1:

输入:

5
         / \
        4   5
       / \   \
      1   1   5

输出:

2  
示例 2:

输入:

1
         / \
        4   5
       / \   \
      4   4   5

输出:

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

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        private int maxL = 0;
        
        public int longestUnivaluePath(TreeNode root) { 
           
            if(root == null) return 0;
            getMaxL(root, root.val);
            return maxL;
        }
        
        private int getMaxL(TreeNode r, int val) { 
            if(r == null) return 0;
            int left = getMaxL(r.left, r.val);
            int right = getMaxL(r.right, r.val);
            maxL = Math.max(maxL, left+right); // 路径长度为节点数减1所以此处不加1
            if(r.val == val) // 和父节点值相同才返回以当前节点所能构成的最长通知路径长度, 否则返回0
                return Math.max(left, right) + 1;
            return 0;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

相关 Java实现 LeetCode 687 最长同值路径（递归）

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

痛定思痛。/ 2023年07月22日 09:28/ 0 赞/ 7 阅读

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

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

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

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

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

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

相关【困难】矩阵最长递增路径 (递归缓存优化)

矩阵最长递增路径先看题目给定一个二维数组 matrix ，可以从任何位置出发，每一步可以向上、下、左、右四个方向移动，返回最大递增路径长度。例子：

缺乏、安全感/ 2022年09月14日 01:53/ 0 赞/ 182 阅读

相关 leetcode687最长同值路径

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

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

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

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

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

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

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

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