Найти минимальную глубину двоичного дерева решение не работает, когда одна сторона дерева равна нулю

Question

Я пытаюсь понять, почему мое решение найти минимальную глубину двоичного дерева не работает, когда одна сторона дерева равна None.

Здесь уже задан вопрос по этому вопросу - Почему мое решение не работает, чтобы найти минимальную глубину двоичного дерева? , но ответ по-прежнему не дает мне понять.

Мой код реализации такой, как показано ниже.

class Solution:
    def minDepth(self, root: 'TreeNode') -> 'int':
        if root is None:
            return 0

        left = self.minDepth(root.left)
        right = self.minDepth(root.right)

        min_depth = min(left, right)

        return 1 + min_depth

Когда последняя строка модифицируется следующим образом, она работает.

    if left == 0 or right == 0:
        return 1 + left + right

    return 1 + min_depth

Мой вопрос: зачем вам проверять, является ли одна сторона None или нет, если в конце вывсе равно суммируйте их все - return 1 + left + right?

Контрольный пример -

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# [1, 2]
root = TreeNode(1)
root.left = TreeNode(2)

solution = Solution()
solution.minDepth(root)

Мой код возвращает 1, где он должен возвращать 2.

EDIT Глубина дерева определяется как количество узлов в кратчайшем пути от корня дерева до листового узла.

Answer 1

Когда вы находитесь на узле, у которого есть только один дочерний элемент, тогда в вашей первой версии кода min_depth для этого узла будет 0 (поскольку один из рекурсивных вызовов вернет 0).

Это действительно неправильно, потому что узел не является листом.Было бы правильно, если бы узел был листом (без дочерних элементов).

В вашем примере корень - это такой узел (с одним дочерним элементом).Вот что происходит:

• minDepth(root) называется
• .... minDepth(root.left) называется
• ........ minDepth(root.left.left) is called and returns 0, because it is Нет`
• ........ minDepth(root.left.right) is called and returns 0, because it is Нет`
• ........ min_depth = min(left, right) оценивается в 0
• ........ возвращаемое значение равно 1 для minDepth(root.left)
• .... minDepth(root.right) вызывается и возвращает 0, потому что это None
• ....min_depth = min(left, right) равно 0, что неверно.
• .... итоговое возвращаемое значение равно 1 (неверно).

Когда вы находитесь в ситуации, когда либо left или right равно 0, вам нужно получить minDepth оставшегося потомка и добавить 1 к нему.Вот почему это работает, когда вы добавляете это:

if left == 0 or right == 0:
    return 1 + left + right