Trying to find the diameter of a binary tree, but I don't know why I'm failing one particular test case

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

Trying to find the diameter of a binary tree, but I don't know why I'm failing one particular test case

问题

在LeetCode上练习算法技能时,遇到了这个问题:https://leetcode.com/problems/diameter-of-binary-tree/

我尝试实现类似于查找树的最大深度的算法。这就是为什么我创建了第二个函数,并且用根节点的左右子节点调用了它。但它并不百分之百地有效,我无法弄清楚。我贴出了它失败的测试用例。

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        return check(root.left) + check(root.right);
    }
    
    public int check(TreeNode root){
        if(root == null) return 0;
        
        return Math.max(check(root.left), check(root.right)) + 1;
    }
}
[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

输出为7,但应该返回8。我将链接贴在了LeetCode问题中,这样您就可以输入测试用例并可视化树。实际上,我不理解为什么应该等于8。根据我的理解,答案应该是7,但显然应该是8。我将其发布在问题的讨论部分,但没有人回复。

英文:

Was practicing my algorithms skills on leetcode, when I came across this question
<https://leetcode.com/problems/diameter-of-binary-tree/>

I tried implementing something similar to finding the max depth of a tree. That's why I created a second function and called it with the left and right child nodes of the root node. But it doesn't 100% work and I can't figure it out. I pasted the test case that it fails.

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        return check(root.left) + check(root.right);
    }
    
    public int check(TreeNode root){
        if(root == null) return 0;
        
        return Math.max(check(root.left), check(root.right)) + 1;
    }
}
[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

The output is 7, but it needs to return 8.
I pasted the link to the leetcode question so you can input the testcase and visualize the tree. I actually don't understand why it should equal 8. From my understanding the answer SHOULD be 7, but it needs to be 8 apparently. I posted it in the discussions part of the question but no ones responded.

答案1

得分: 2

你计算直径的方法是错误的。它假设任何节点之间的最长路径都通过根节点。注意,问题警告你不要做出这个假设:

这个路径可能通过根节点,也可能不通过。

你的代码找到了路径 [7, 4, -3, -9, 9, 6, 0, -1],长度为7,但是如果你避免根节点,存在一条更长的路径 [-1, 0, 6, 9, -9, -7, -6, 9, 2],长度为8。在这条路径中,我们从叶节点 -1 上升四层到 -9,然后再通过 -7 右侧的 -6 下降另外四层到达叶节点 2。

英文:

Your approach to calculating the diameter is wrong. It assumes that the longest path between any nodes goes through the root. Note that the question warns you against making this very assumption:

> This path may or may not pass through the root.

Your code finds the path [7, 4, -3, -9, 9, 6, 0, -1], of length 7, but there is a longer path if you avoid the root node, [-1, 0, 6, 9, -9, -7, -6, 9, 2], and this has length 8. In this path, we head from leaf node -1 up four levels to -9 and then back down another four layers to leaf node 2 via the -6 on the right of -7.

huangapple
  • 本文由 发表于 2020年10月5日 01:09:40
  • 转载请务必保留本文链接:https://go.coder-hub.com/64197553.html
匿名

发表评论

匿名网友

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

确定