Ошибка при нахождении полной глубины двоичного дерева

Question

Я хочу проверить общую глубину двоичного дерева, поэтому написал следующий код:

    def nodeDepths(root):
        return depthSum(root, 0)
        
    def depthSum(node, depth)
        if node.left:
            depth += depthSum(root.left, depth+1)
        if node.right:
            depth += depthSum(root.right, depth+1)
        return depth
        
    # This is the class of the input binary tree.
    class BinaryTree:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None

Затем я обнаружил следующую ошибку, дайте мне знать, как ее исправить.

Traceback (последний вызов последним): файл «main.py», строка 7, в файле import json_wrapper «/tester/json_wrapper.py», строка 3, в файле программы импорта «/tester/program.py», строка 4 def depthSum (node, depth) ^ SyntaxError: неверный синтаксический статус выхода 1

Answer 1

Ну во-первых, прочтите ошибку: P. У вас есть синтаксическая ошибка в строке 4 и отсутствует : в конце вашего def.

Что касается вашего алгоритма, не совсем уверен, почему у вас есть функция nodeDepths, это не очень помогает.

Для вашей функции depthSum сразу же ваш алгоритм никогда не завершится, поскольку вы застряли в бесконечном рекурсивном l oop - вы никогда не пересекаете дерево из-за использования root вместо node в вашей функции depthSum.

Взгляните на это, это простой способ проверить глубину:

def traverse(root, depth=0):
    if root:
        return max(traverse(root.left, depth+1), traverse(root.right, depth+1))

и просто вызвать его напрямую с помощью

traverse(root)

Я не вижу варианта использования функции nodeDepths.