为什么我的递归深度优先搜索函数返回了错误的值？

huangapple
go评论103阅读模式
英文:

Why is my recursive dfs function returning the wrong value?

问题

尝试解决LeetCode问题，但在这个树问题上卡住了。我的解决方案无法通过下面的测试用例，但我尝试调试了一下也没弄清楚为什么。当我检查代码时，在我的代码中得到了正确的答案。希望有人能告诉我我做错了什么。谢谢
以下是测试用例失败的情况以及我在Java中的代码

  1. [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]
  1. class Solution {
  2.     int longestPath = 0;
  3.     public int longestUnivaluePath(TreeNode root) {
  4.         dfs(root, root.val);
  5.         
  6.         return longestPath ;
  7.     }
  8.     
  9.     public int dfs(TreeNode root, int value){
  10.         if(root == null) return 0;
  11.         
  12.         int leftPath = dfs(root.left, root.val);
  13.         int rightPath = dfs(root.right, root.val);
  14.         
  15.         longestPath = Math.max(longestPath, leftPath + rightPath);
  16.         
  17.         int val = (root.val == value) ? 1 : 0;
  18.         return Math.max(leftPath, rightPath) + val;
  19.     }
  20. }
英文:

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

  1. [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]
  1. class Solution {
  2.     int longestPath = 0;
  3.     public int longestUnivaluePath(TreeNode root) {
  4.         dfs(root, root.val);
  5.         
  6.         return longestPath ;
  7.     }
  8.     
  9.         public int dfs(TreeNode root, int value){
  10.         if(root == null) return 0;
  11.         
  12.         int leftPath = dfs(root.left, root.val);
  13.         int rightPath = dfs(root.right, root.val);
  14.         
  15.         longestPath = Math.max(longestPath, leftPath + rightPath);
  16.         
  17.         int val = (root.val == value) ? 1 : 0;
  18.         return Math.max(leftPath, rightPath) + val;
  19.     }
  20. }

答案1

得分: 1

看起来不错！

需要修改返回条件。以下代码将会通过：

  1. class Solution {
  2.     int longestPath = 0;
  3.     public int longestUnivaluePath(TreeNode root) {
  4.         if (root == null) {
  5.             return 0;
  6.         }
  7.         
  8.         dfs(root, root.val);
  10.         return longestPath ;
  11.     }
  13.     public int dfs(TreeNode root, int value) {
  14.         if (root == null) {
  15.             return 0;
  16.         }
  18.         int leftPath = dfs(root.left, root.val);
  19.         int rightPath = dfs(root.right, root.val);
  21.         longestPath = Math.max(longestPath, leftPath + rightPath);
  23.         return root.val == value ? 1 + Math.max(leftPath, rightPath) : 0;
  24.     }
  25. }
英文:

Looks good!

The return condition has to be modified. This'll pass:

  1. class Solution {
  2.     int longestPath = 0;
  3.     public int longestUnivaluePath(TreeNode root) {
  4.         if (root == null) {
  5.             return 0;
  6.         }
  7.         
  8.         dfs(root, root.val);
  10.         return longestPath ;
  11.     }
  13.     public int dfs(TreeNode root, int value) {
  14.         if (root == null) {
  15.             return 0;
  16.         }
  18.         int leftPath = dfs(root.left, root.val);
  19.         int rightPath = dfs(root.right, root.val);
  21.         longestPath = Math.max(longestPath, leftPath + rightPath);
  23.         return root.val == value ? 1 + Math.max(leftPath, rightPath) : 0;
  24.     }
  25. }

huangapple
  • 本文由 发表于 2020年10月11日 05:32:28
  • 转载请务必保留本文链接：https://go.coder-hub.com/64298510.html
  • algorithm
  • data-structures
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定