【二叉树】最长同值路径
题目描述
给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
两个节点之间的路径长度 由它们之间的边数表示。
示例 1:
输入：root = [5,4,5,1,1,null,5]
输出：2
解题思路
这道题我想是用DFS解决，但是做了一会儿发现没有想清楚递归公式，最终还是查看了其他人的解法。
整个递归思路如下：
- 找到(左子树+当前节点)的长度，设置为countLeft；
- 找到(右子树+当前节点)的长度，设置为countRight；
- max = Math.max(max, countLeft+countRight);
- 返回Math.max(countLeft, countRight).
图示如下：
第一阶段
拆分成左子树：
那么左子树中没有一条边上的2个节点相等，返回0，max=0
右子树：
那么右子树中有一条边上的2个节点相等，返回1，max=1
第二阶段
根节点5，同左子树的根节点4比较，发现不相等，countLeft=0；
根节点5，同右子树的根节点5比较，发现相等，由于右子树已经返回1，则countRight=2；
最终计算max = Math.max(max, countLeft+countRight) = 2;
具体代码实现如下：
import org.example.TreeNode;
class Solution {
int max = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root != null) {
int left = dfs(root.left);
int right = dfs(root.right);
int countLeft = 0;
if (root.left != null && root.left.val == root.val) {
countLeft = left + 1;
}
int countRight = 0;
if (root.right != null && root.right.val == root.val) {
countRight = right + 1;
}
max = Math.max(max, countLeft + countRight);
return Math.max(countLeft, countRight);
} else {
return 0;
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(4);
root.left = new TreeNode(4);
root.right = new TreeNode(4);
root.left.left = new TreeNode(4);
root.right.left = new TreeNode(4);
Solution solution = new Solution();
System.out.println(solution.longestUnivaluePath(root));
}
}总结
这道题是中等难度，这道题使用dfs做是很高效的，代码复杂度也不高，主要困难点是找到规律能通过左右子树来计算满足条件的边数量。如果有更加高效、简洁的代码实现欢迎回复。