二叉树的直径在 104 个测试用例中有 4 个失败

Question

我正在研究 Leet Code 问题 543. Diameter of Binary Tree:

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1

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

这是我的尝试：

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

我通过了 100/104 个测试用例。

我出错的测试用例的输入是 [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]，预期结果是 8。但是，由于我的解决方案的逻辑，我得到了 7 并且不知道我怎么会错。

Answer 1

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.

提供的树如下所示：

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

最长路径确实是 8，因为以 -9 为根的子树中的最长路径具有最长路径。您的代码找不到最长路径，因为它要求根是其中的一部分。

因此，您应该（递归地）检查任何子树的最长路径是什么，并保留这些选项中最长的：

在左子树中找到的最长路径
在右子树中找到的最长路径
包含根的最长路径（即左高+右高+1）

您的代码没有考虑前两个选项，而总是考虑第三个选项。

以上是在这个（隐藏的）解决方案中实现的。先自己试试：

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!

Answer 2

您的代码假定 diameter of the binary tree 将始终通过 root，但事实并非如此。您必须考虑直径较长的子树。一种方法可以在下面找到，它是您的代码的略微修改版本：

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)

已测试，它通过了所有测试用例。
主要逻辑是保留子树的最大直径值，并将其与最后通过根的直径进行比较。

二叉树的直径在 104 个测试用例中有 4 个失败

Diameter of binary tree fails 4 out of 104 test cases

python

algorithm

binary-tree

graph

data-structures

Example 1