二叉树的直径

Question

我正在研究一个名为二叉树直径的着名问题。我知道这已经多次讨论过（Diameter of Binary Tree），但解释似乎并不正确。特别是，单个节点树应返回0而不是1（我从Leetcode自己的检查器中检查）。无论如何，这是问题陈述：

给定二叉树，您需要计算树的直径长度。二叉树的直径是树中任意两个节点之间最长路径的长度。此路径可能会也可能不会通过根目录。

答案分别为0,1和5。从第一眼看，似乎计算左子树的边数和右子树的数量应该得出答案。

所以我开始使用postorder递归（自下而上）：

max_diameter = 0
def getDiameter(node):
    if node is NULL:
        return 0 

    left_diameter = getDiameter(node.left)
    right_diameter = getDiameter(node.right)

    max_diameter = max(left + right, max_diameter)

到现在为止还挺好。但代码不起作用，我很难理解那里的一些解决方案。例如：

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0

        def depth(p):
            if not p: return 0
            left, right = depth(p.left), depth(p.right)
            self.ans = max(self.ans, left+right)
            return 1 + max(left, right)

        depth(root)
        return self.ans

为什么要比较左子树和右子树？为什么+ 1？还有，有人说找高度，有人说找到深度。这令人困惑，我觉得人们只是在那里抛出条款......任何澄清都是有帮助的。

Answer 1

最长的路径总是从一个叶子到一个节点，然后再回到另一个叶子。从节点看，该路径的长度为左子树的最大深度和右子树的最大深度之和。

我们不能只将它应用于根节点，因为您的第三个示例显示节点可能位于树中的任何位置。因此，您必须测试所有节点并获得最大解决方案：

diameter (Leaf)     = 0
diameter (Node l r) = max(diameter l, diameter r, depth l + depth r)

depth (Leaf)     = 0
depth (Node l r) = 1 + max(depth l, depth r)

您发现的解决方案递归计算所有节点的深度，并且沿途还会更新self.ans插槽中的最大直径。