试图做一个leetcode问题,但我坚持这一一棵树的问题。https://leetcode.com/problems/longest-univalue-path/
我的解决方案不适用于以下测试用例,但我尝试对其进行调试,无法弄清原因。当我查看它时,我在代码中得到了正确的答案。希望有人能告诉我我做错了什么。谢谢下面是它失败的测试用例和我在Java中的代码
[5,4,5,4,4,5,3,4,4,null,null,null,4,null,null,4,null,null,4,null,4,4,null,null,4,4]
class Solution {
int longestPath = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root, root.val);
return longestPath ;
}
public int dfs(TreeNode root, int value){
if(root == null) return 0;
int leftPath = dfs(root.left, root.val);
int rightPath = dfs(root.right, root.val);
longestPath = Math.max(longestPath, leftPath + rightPath);
int val = (root.val == value) ? 1 : 0;
return Math.max(leftPath, rightPath) + val;
}
}
返回条件必须修改。这将通过:
class Solution {
int longestPath = 0;
public int longestUnivaluePath(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root, root.val);
return longestPath ;
}
public int dfs(TreeNode root, int value) {
if (root == null) {
return 0;
}
int leftPath = dfs(root.left, root.val);
int rightPath = dfs(root.right, root.val);
longestPath = Math.max(longestPath, leftPath + rightPath);
return root.val == value ? 1 + Math.max(leftPath, rightPath) : 0;
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句