为什么我的递归dfs函数返回了错误的值

Question

试图做一个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;
}
}

Answer 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;
}
}