共计 1477 个字符，预计需要花费 4 分钟才能阅读完成。
一、题目：
给定一个二叉树，找到最长的门路，这个门路中的每个节点具备雷同值。这条门路能够通过也能够不通过根节点。
留神：两个节点之间的门路长度由它们之间的边数示意。
示例 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;
}
}
正文完
