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

素颜马尾好姑娘i 2023-10-05 17:42 44阅读 0赞

#### 文章目录 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

**注意：两个节点之间的路径长度由它们之间的边数表示。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

这题虽然题目说可不经过根节点，但是我们就以根节点出发。

我们只需要找到根节点的左子树的 相同值的 最长路径。和右子树的…。然后再把二者的长度加起来。

为了实现这个功能我们就需要一个辅助函数。  
当然，如果类似于\[1,2,3\]这样的树，那么用辅助函数返回的左子树的和右子树的相同值最大路径就是0.即结果也是0.并不会影响最终结果。

这里在着重解释一下辅助函数的返回值的意思。

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

## 代码 ##

class Solution {
        
        int res=0;
        public int longestUnivaluePath(TreeNode root) {
        
            help(root);
            return res;
        }
    
        public int help(TreeNode root){
        
            /*
            这个方法的功能就是，我传过来是左子树的时候，返回给我一个左子树的最长路径的最大值。
            用在右子树的时候同理。
            */
    
    
            if(root==null){
        
                return 0;
            }
            int leftCount=help(root.left);//用来保存左子树的最长路径的最大值
            int rightCount=help(root.right);//用来保存右子树的最长路径的最大值
            int left=0,right=0;//对于root来说，分别保存root左/右子树的最长路径
    
            if(root.left!=null&&root.left.val==root.val){
        //root的左子树不为空且值和root相同
                left=leftCount+1;//那么对于root来说左子树的最长路径就要+1
            }
            if(root.right!=null&&root.right.val==root.val){
        //root的右子树不为空且值和root相同
                right=rightCount+1;//那么对于root来说右子树的最长路径就要+1
            }
    
            res=Math.max(res,left+right);//注意！！更新结果在这里。对根节点来说，最长相同路径那就是左子树最长路径+右子树最长路径（假如右子树没有相同值那么right就是0，不影响最终结果）。用res来维护最大值
    
            return Math.max(left,right);//这个方法不用更改res，因为这个方法的目的是为了找出子树最长路径的最大值。 具体什么意思见CSDN
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210113235805808.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210114001027820.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70