给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

Solution:

有三种不同的情况：

左边子树路径最长，在左子树中若相同根节点不同则置为0，相同加一

右边子树路径最长，在有子树中若是相同根节点不同则置为0，相同加一

左右子树加上根节点路径最长。

/**

* Definition for a binary tree node.

* public class TreeNode {

*    int val;

*    TreeNode left;

*    TreeNode right;

*    TreeNode(int x) { val = x; }

* }

*/

class Solution {

    private int max = 0;

    public int longestUnivaluePath(TreeNode root) {

        path(root,root);

        return max;

    }

    public int path(TreeNode node,TreeNode root){

        if(root==null||node==null) return 0;

        int left = path(node.left,node);         //左边路径和

        int right = path(node.right,node);    //右边路径和

        left = (node.left!=null&&node.left.val==node.val)?left+1:0;

        right = (node.right!=null&&node.right.val==node.val)?right+1:0;

        max = Math.max(left+right,max);   //取最大

        return Math.max(left,right);           //返回左右子树中的最大值。

    }

}