英文:
Why is my recursive dfs function returning the wrong value?
问题
尝试解决LeetCode问题，但在这个树问题上卡住了。我的解决方案无法通过下面的测试用例，但我尝试调试了一下也没弄清楚为什么。当我检查代码时，在我的代码中得到了正确的答案。希望有人能告诉我我做错了什么。谢谢
以下是测试用例失败的情况以及我在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;
}
}
英文:
Trying to do a leetcode problem but Im stuck on this one tree question. https://leetcode.com/problems/longest-univalue-path/
My solution doesn't work for the below test case but I tried to debug it and couldnt figure out why. When I go over it, I get the correct answer in my code. Hoping someone can tell me what Ive done wrong. Thank you
Below is the test case it fails and my code in 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;
}
}
答案1
得分: 1
看起来不错！
需要修改返回条件。以下代码将会通过：
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;
}
}
英文:
Looks good!
The return condition has to be modified. This'll pass:
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;
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论