题目
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出: 2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出: 2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
解题思路
我们定义函数longestUnivalue返回左右两边其中最大的路径长度，此时我们有四种情况考虑
root.left == root == root.right
root.left == root
root.right == root
root.left ！= root != root.right
对于第一种情况此时左右孩子和根相同，需要更新的最大长度res=max(res,l+r+2)，并且返回max(l,r)+1
对于第二种情况，此时左孩子和根相同，需要更新最大长度res=max(res,l+1)，并且返回l+1
对于第三种情况，此时右孩子和根相同，需要更新最大长度res=max(res,r+1)，并且返回r+1。
对于第四种情况，此时只需返回0即可。
代码实现
public int visitTreeLongestPath(Node node) {
if (node == null) {
return 0;
}
int left = visitTreeLongestPath(node.left);
int right = visitTreeLongestPath(node.right);
if (node.left != null && node.left.value == node.value &&
node.right != null && node.right.value == node.value) {
Math.max(currentMax, left + right + 2);
return Math.max(left, right) + 1;
}
if (node.left != null && node.left.value == node.value) {
int value = left + 1;
Math.max(currentMax, value);
return value;
}
if (node.right != null && node.right.value == node.value) {
int value = right + 1;
Math.max(currentMax, value);
return value;
}
return 0;
}
类似问题
- Leetcode 124：二叉树中的最大路径和（超详细的解法！！！）
- Leetcode 543：二叉树的直径（超详细的解法！！！）
参考: https://blog.csdn.net/qq_17550379/article/details/87380945
