687. Longest Univalue Path

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;
    }
}