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

一、题目：

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


}