关于算法:力扣最长同值路径

一、题目：

给定一个二叉树，找到最长的门路，这个门路中的每个节点具备雷同值。 这条门路能够通过也能够不通过根节点。
留神：两个节点之间的门路长度由它们之间的边数示意。
示例 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;
    }


}