Diameter of binary tree fails 4 out of 104 test cases-CodePudding

I am working on Leet Code problem

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

This is my attempt:

def diameterOfBinaryTree(self, root):
    return self.getHeight(root.left)   self.getHeight(root.right)

def getHeight(self, root):
    if not root:
        return 0
    return max(self.getHeight(root.left), self.getHeight(root.right))   1

I got 100/104 test cases passed.

The test case that I got wrong had an input of [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] with an expected result of 8. However, due to the logics of my solution, I got 7 instead and have no idea how I could be wrong.

CodePudding user response：

You code assumes that diameter of the binary tree will always go through the root, which is not the case. You have to consider the subtrees with longer diameters. One way to do it can be found below, it is a slightly modified version of your code:

class Solution(object):
    maximum = 0
    def getHeight(self, root):
        if not root:
            return 0
        left =  self.getHeight(root.left)
        right =  self.getHeight(root.right)
        sub_diameter = left   right
        if(self.maximum < sub_diameter): self.maximum = sub_diameter
        return max(left, right)   1
    def diameterOfBinaryTree(self, root):
        return max(self.getHeight(root.left)   self.getHeight(root.right), self.maximum)

Tested, it passes all testcases.
Main logic is to keep the maximum diameter value for subtrees and compare it with the diameter that goes through the root at the end.

CodePudding user response：

The only test case that I got wrong had an input of [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] ... have no idea how I could be wrong.

The provided tree looks like this:

                ___4___
               /       \
             -7     ___-3_____
                   /          \
              ___-9___        -3
             /        \       /
            9         -7    -4
           /          / \
        __6__       -6  -6
       /     \      /   /
      0       6    5   9
       \     /        /
       -1  -4       -2

The longest path is indeed 8, because the longest path in the subtree rooted at -9 has that longest path. Your code does not find that longest path because it requires that the root is part of it.

So, you should check what the longest path is for any subtree (recursively) and retain the longest among these options:

The longest path found in the left subtree
The longest path found in the right subtree
The longest path that can be made by including the root (i.e. left-height right-height 1)

Your code does not take the two first options into account and always goes for the third.

The above is implemented in this (hidden) solution. First try it yourself:

class Solution(object):
def diameterOfBinaryTree(self, root):
self.longestPath = 0

def levels(node): # With side-effect: it updates longestPath
if not node:
return 0
leftLevels = levels(node.left)
rightLevels = levels(node.right)
self.longestPath = max(self.longestPath, leftLevels rightLevels)
return 1 max(leftLevels, rightLevels)

levels(root) # Not interested in the returned value...
return self.longestPath # ...but all the more in the side effect!