给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
解答
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int longestLen = 0;
public int longestUnivaluePath(TreeNode root) {
// 双重递归。第一层递归递归树，第二层递归递归这个值为根结点时，构成的最长同值路径
dfsLongestUnivaluePath(root);
return longestLen;
}
public void dfsLongestUnivaluePath(TreeNode node) {
if (node != null) {
getLongestUnivalue(node);
if (node.left != null) dfsLongestUnivaluePath(node.left);
if (node.right != null) dfsLongestUnivaluePath(node.right);
}
}
// 计算当前节点为根节点时，最大的同值路径长度
public int getLongestUnivalue(TreeNode node) {
if (node == null) return 0;
int left = 0, right = 0;
if (node.left != null && (node.val == node.left.val))
left = getLongestUnivalue(node.left)+1;
if (node.right != null && (node.val == node.right.val))
right = getLongestUnivalue(node.right)+1;
longestLen = Math.max(longestLen, left+right);
return Math.max(left, right);
}
}
