图解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^)/ ~ 「干货分享，每天更新」