Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
Note: The length of path between two nodes is represented by the number of edges between them.
Example 1:
Input:
5
/ \
4 5
/ \ \
1 1 5
output:2
Example 1:
Input:
1
/ \
4 5
/ \ \
4 4 5
output:2
一刷：
题解：
用pre-order traverse
分别计算出左右branch的path长度。并在计算时update max path.
max = Math.max(max, left+right+1)
如果自己跟parent值相同，返回自己+max(left, right)
否则返回0。
并且由于自己计算的max为node数目，于是真正的解是max-1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int max = 0;
public int longestUnivaluePath(TreeNode root) {
if(root == null) return 0;
helper(root, root.val);
return max == 0? 0:max-1;
}
public int helper(TreeNode root, int target){
if(root == null) return 0;
int left = helper(root.left, root.val);
int right = helper(root.right, root.val);
max = Math.max(left + right + 1, max);
if(root.val==target)return Math.max(left, right)+1;
else return 0;
}
}
