Диаметр бинарного дерева

Question

Я работаю над известной проблемой, которая называется Диаметр бинарного дерева.Я знаю, что это обсуждалось много раз ( Диаметр бинарного дерева ) здесь, но объяснение кажется неправильным.В частности, одиночное дерево узлов должно возвращать 0, а не 1 (я проверил из собственной проверки Leetcode).В любом случае, вот формулировка проблемы:

Для заданного бинарного дерева вам нужно вычислить длину диаметра дерева.Диаметр бинарного дерева - это длина самого длинного пути между любыми двумя узлами в дереве.Этот путь может проходить или не проходить через корень.

Ответы 0, 1 и 5 соответственно.С первого взгляда кажется, что вычисляется количество ребер левого поддерева, а число правого поддерева должно дать ответ.

Итак, я начал с рекурсии по порядку (снизу вверх):

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.