力扣——最长同值路径

一、题目：

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

二、思路：

这道题的题意就是找出二叉树，最长同值路径。
分为两种情况
（1）从根节点出发，左子树的最长同值路径
（2）从根节点出发，右子数的最长同值路径
而有一种特殊的是，根节点在中间，就比如实例2的同值4，这种，只需要再我们遍历二叉树的时候，去判断，是否 左右子节点与根节点相等就行了，那么与就需要最长路径就需要+2，（1）（2）就只需要+1。
对于二叉树这种数据结构，很明显的使用递归去遍历左右子树就行了。

三、代码：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
public class 最长同值路径 {
    static int ans;

    public static void main(String[] args) {
        //第一层
        TreeNode node = new TreeNode(1);
        //第二层
        node.left = new TreeNode(4);
        node.right = new TreeNode(4);
        //第三层
        node.left.left = new TreeNode(4);
        node.left.right = new TreeNode(4);
        node.right.right = new TreeNode(5);

        System.out.println(longestUnivaluePath(node));
    }

    public static int longestUnivaluePath(TreeNode root) {
        ans = 0;
        longestPath(root);
        return ans;

    }
    //递归函数功能：搜寻以node为起点的最长同值路径:要么是以node为起点的左子树，要么是以node为起点的右子树
    public static int longestPath(TreeNode node) {
        if (node == null) return 0;
        int maxLorRres = 0;
        int left = longestPath(node.left); //node左子树的最长同值路径
        int right = longestPath(node.right);//node右子树的最长同值路径
        //这种情况对于寻找最长同值路径长有帮助，对于搜索以root为路径起始点的最长路径没有帮助
        if (node.left != null && node.left.val == node.val && node.right != null && node.right.val == node.val) {
            ans = Math.max(ans, left + right + 2);
        }
        //从左右子树中选择最长的同值路径
        if (node.left != null && node.left.val == node.val) {
            maxLorRres = left + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            maxLorRres = Math.max(maxLorRres, right + 1);
        }
        //从ans与maxLorRres中更新最大值
        ans = Math.max(ans, maxLorRres);
        //返回节点的左右最大的同值的值
        return maxLorRres;
    }


}