#leetcode687.最长同值路径

 

 最长同值路径，就是相同值组成的节点路径中最长的路径的边的个数，不要求一定是从根节点到叶子节点。

所以，先看下题解的代码：

int maxPath = 0;
    //给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return maxPath;
    }

    public int dfs(TreeNode root) {

        if(root == null)
            return 0;

        int left = dfs(root.left);
        int right = dfs(root.right);

        int leftPath = root.left !=null && root.left.val == root.val ? left + 1 : 0;
        int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;

        maxPath = Math.max(maxPath, leftPath + rightPath);

        return Math.max(leftPath, rightPath);
    }

设置一个全局变量maxPath;然后是调用dfs递归函数。dfs是深度优先遍历；

如果root == null的情况下直接返回0；

然后是深度优先遍历 int left = dfs(root.left) + int right = dfs(root.right);

left和right返回的结果后续再分析

接下来是本题目的重点，就是 如果左节点的val和当前root节点的val相等，那么leftPath就可以在当前的left返回值上+1，而如果不相等则直接清零；

同理，如果右节点的val和root的val相等的话，rightPath的值可以在当前的right的返回值上+1，而如果不相等，的话同样也需要清零；

最后是返回值问题，因为它决定了left和right值的具体意义，这边是Math.max(leftPath, rightPath)

就是说当前函数作用域内的主节点的最大可能的路径的数目；这样逐渐积累，当回溯到根节点的时候，就能得到同值的最大路径的长度了；