问题

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

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

示例 1:

输入:

      5
     / \
    4   5
   / \   \
  1   1   5

输出 \(2\)

示例 2:

输入:

      1
     / \
    4   5
   / \   \
  4   4   5

输出: \(2\)
注意: 给定的二叉树不超过\(10000\)个结点。 树的高度不超过\(1000\)。

解法

基本想法就是深度优先遍历。遍历时，判断左右儿子的值与自己的值是否相等，相等则result++，否则置为0即可。没有什么难度。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    public int longestUnivaluePath(TreeNode root) {
        if (root != null) {
            dfs(root);
        }
        return result;
    }
    private int dfs(TreeNode root) {
        if (root ==null) {
            return 0;
        }
        
        //计算左子树的同值路径
        int left = dfs(root.left);
        //判断左儿子与自己的值是否相等，相等则++ 否则置为0
        if (root.left == null || root.val !=root.left.val) {
            left = 0;
        } else {
            left ++;
        }
        //计算右子树的同值路径
        int right = dfs(root.right);
        //同左儿子的判断
        if (root.right == null || root.val !=root.right.val) {
            right = 0;
        } else {
            right ++;
        }
        //需要注意的是这里的max为left+right与result的判断。
        result = Math.max(left + right,result);
        return Math.max(left, right);
    }
}