图解LeetCode——687. 最长同值路径（难度：中等）

一、题目

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

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

二、示例

2.1> 示例 1:

【输入】root = [5,4,5,1,1,5]
【输出】2
【解释】5——>5——>5

2.2> 示例 2:

【输入】root = [1,4,5,4,4,5]
【输出】2
【解释】4——>4——>4

提示:

• 树的节点数的范围是 [0, 10^4] 
• -1000 <= Node.val <= 1000
• 树的深度将不超过 1000

三、解题思路

根据题目描述，我们需要在一个指定的二叉树上，找到一个最长的路径长度，这个路径有什么特点呢？就是路径上所有节点的值要一致。那么，既然是要对二叉树进行操作，我们常用的就是深度遍历和广度遍历了。那么，本题涉及到的是相同值的节点路径长度的判断，那么，符合深度遍历的解题方式 ，也就是说，针对每条分支去判断，如果发现节点不同了，那么则结束路径长度统计，开启新的路径长度统计。

那么，既然是统计路径长度，下面我列出了5种树的形状，其实，大体上，应该是3种：

第一种：相同值的节点在同一侧。如：形状1和性状2；
第二种：相同值的节点组成最小二叉树结构，即：根节点+左子树节点+右子树节点。如：形状3；
第三种：第一种和第二种的组合。如：形状4和性状5;

细心的同学会发现，你说的第一种和第三种其实也是一样的啊，第一种只不过是树节点缺少了左子树或者右子树啊。其实是这样子的，但是为了便于理解下面要介绍的路径长度计算，此处暂时把它们归为了两类。其实，最终我们会发现，无论是哪种形状，都是多个形状3的拼装而已，区别就是左右子树是否存在。

现在，我们再来看一下如何计算路径长度，我们拆分一下形状1和形状4，发现它们的路径长度，就是可以拆分的最小二叉树的个数。如下所示：

那么在解这道题的是，就变成了计算最小二叉树的个数了，由于路径计算是累加的，所以，每当我们要将累加值返回给父节点的时候，是根据左子树和有子树累积的长度谁更大，以谁为准。请看下图：

上面就是大致的解题思路了。具体实现，请参照下面四：代码实现部分

四、代码实现

class Solution {
    int result = 0;
    public int longestUnivaluePath(TreeNode root) {
        calculate(root);
        return result;
    }
    public int calculate(TreeNode node) {
        if (node == null) return 0;
        int leftValue = calculate(node.left);
        int rightValue = calculate(node.right);
        leftValue = (node.left != null && node.val == node.left.val) ? ++leftValue : 0; 
        rightValue = (node.right != null && node.val == node.right.val) ? ++rightValue : 0;
        result = Math.max(result, leftValue + rightValue);
        return Math.max(leftValue, rightValue);
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」