给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
分析：
1.如果不仔细观察，很容易陷入到一个TreeNode误区，对于用java解答的小伙伴，在IDE中解这道题，很容导包 import javax.swing.tree.TreeNode;，结果发现，这个TreeNode是个interface呀，这怎么办？难道要找它的实现子类？一脸茫然。淡定，这个时候就需要考验审题能力了，在平台给出的答案区上方给出了注释状态的一段代码，不知道读者有没有留意到？
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
其实这个就是本题需要的TreeNode，当我们在平台上提交答案的时候，不需要定义这个class，平台验收答案时是带着这个实现的；而当我们在IDE上进行编码调试的时候，需要把这个TreeNode代码拷贝到IDE中，解开注释。然后，就可以正式开始解题了。
2.我们来分析一下题目的关键点。
二叉树：一个节点只有两个子节点，左和右。
路径：节点与节点之间的连线就是一条路径
同值路径：节点和与子节点或者父节点之间的值相同，那么这就是一条同值路径，本题求的就是这个最大值。
边数：可以理解为题目示例中连接节点的直线。
3.这一类问题，需要用递归的方法解决。在二叉树中，只能从根节点向下递归调用，可以通过root.left和root.right的方法得到两个子节点的TreeNode对象，由此一层一层递归调用下去，直到最底端的叶节点。
4.第一个可能遇到的坑：如果当前节点与左节点的值不同，那么左边的同值路径就会断掉，同理，如果和右节点值不同，右边的同值路径就会断掉。一旦断掉，那么当前节点的同值路径值就应该清零。
5.第二个可能遇到的坑：如果当前节点与子节点的值不同，那么从子节点连过来的同值路径就断掉了，而如果当前节点和父节点的值相同，需要注意，会从本节点向父节点连一个新的同值路径，与从子节点来的同值路径无关，不可累加。本题求解的是多条同值路径中最长的那条。
6.第三个可能遇到的坑：先看下图，这是平台在验证答案时给出的测试用例。
平台测试用例.png
看图，这个二叉树的最大同值路径就是由根节点26组成的路径，从根节点开始，能连起来的，值为26的节点一共是6个，它们之间的连线一共是5条，那么答案就是5吗？NONO，平台的期望值是4，明白了吗？这里有一个隐含条件，同值路径必须是单向的，就是用纸笔能一笔画完的，不能倒退着连。
根据这些分析，java解答如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int longestUnivaluePath(TreeNode root) {
if (root == null) {
return 0;
}
int[] longestPath = new int[1];
getUnivaluePathCount(root, longestPath);
return longestPath[0];
}
private int getUnivaluePathCount(TreeNode node, int[] longestPath) {
int left = 0;
if (node.left != null) {
left += getUnivaluePathCount(node.left, longestPath);
if (node.val == node.left.val) {
/* 如果本节点和左节点值相同，路径能继续，再累加1 */
left += 1;
} else {
/* 否则，就说明左边的路径已经断开，本节点的左方向的单向路径值清零 */
left = 0;
}
}
int right = 0;
if (node.right != null) {
right += getUnivaluePathCount(node.right, longestPath);
if (node.val == node.right.val) {
/* 如果本节点和右节点值相同，路径能继续，再累加1 */
right += 1;
} else {
/* 否则，就说明右边的路径已经断开，本节点的右方向的单向路径值清零 */
right = 0;
}
}
int currentLongestPath;
if (node.left != null && node.right != null && node.left.val == node.right.val) {
/* 如果左右节点的值相同，那么可以相加连接起来。但如果左右相同但和本节点值不同，那么left和right的值都是0 */
currentLongestPath = left + right;
} else {
/* 否则，最大的路径值只能是左右路径的最大值 */
currentLongestPath = Math.max(left, right);
}
if (currentLongestPath > longestPath[0]) {
/* 最终返回的结果在这里，每次递归都是以当前节点为核心，计算最大路径值，在多次递归当中，仅保留最大的值 */
longestPath[0] = currentLongestPath;
}
/* 递归返回的是本节点与左右两个子节点的同值路径的最大值，注意，如果本节点的值与左右节点的值都不同，那么返回的是0 */
return Math.max(left, right);
}
}
最后说一下，本答案中的 int[] longestPath 用的java引用传递的特性，这并不是唯一的方法，还可以定义一个成员变量 private int longestPath; 来记录所有的递归过程最大的同值路径，那样会让递归方法少一个参数，在大量的递归调用过程中速度会更快。希望读者们能学到这两种方法，在今后的开发中根据实际情况合理使用。
网友评论