英文:
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论