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

go评论53阅读模式

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

# 问题

``````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]
``````

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

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.

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

go 54

go 64

go 66

go 66