Обратите внимание, что алгоритм нахождения высоты дерева одинаков как для двоичных деревьев поиска, так и для общих двоичных деревьев, поэтому для целей этого обсуждения я буду игнорировать BST.
Этот код не совсем понятен, поэтому я не виню вас за то, что вы его не поняли.
Вот переписать, чтобы сократить шум:
from collections import namedtuple
Node = namedtuple("Node", "data left right")
def height(root):
return max(height(root.left), height(root.right)) + 1 if root else 0
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^ ^^^^^^
# | | |
# | | base case; root is None
# | add the current node's height
# recursively find the maximum height of the current node's children
if __name__ == "__main__":
""" 1
/ \
2 3
\ /
4 5
\
6
"""
root = Node(
1,
Node(
2,
None,
Node(4, None, None)
),
Node(
3,
Node(
5,
None,
Node(6, None, None)
),
None
)
)
print(height(root)) # => 4
Теперь у нас есть два случая в данном вызове height:
root равно None, и в этом случае мы возвращаем 0, потому что у нас ничего нет. Это наш базовый случай или условие, которое завершает рекурсию. root не равно None, и в этом случае мы возвращаем 1, чтобы подсчитать высоту текущего рассматриваемого узлаэтим конкретным рекурсивным вызовом плюс максимум высоты левого и правого поддеревьев, укорененных в текущем узле. Это критический рекурсивный шаг.
Давайте пройдемся по вызову к height в приведенном выше примере дерева.
Сначала мы посетим узел {1} в качестве нашего корня. Это не базовый случай, поэтому {1} запрашивает у своего левого потомка {2} максимальную высоту. {2} также не является базовым случаем, поэтому он запрашивает у своего левого потомка, None. None является нашим первым базовым случаем и возвращает 0 обратно к {2}. {2} затем спрашивает высоту своего правого потомка, {4}. {4} - это лист с двумя пустыми None ссылками, которые возвращают 0, но {4} добавляет 1 для себя и возвращает это {2}.
Узел {2} теперь может вычислять max(height(root.left), height(root.right)), что составляет max(0, 1) => 1, а {2} может добавить 1, чтобы подсчитать собственную высоту и сообщить {1}, общее число 2.
Наш корень {1} теперь имеет высоту 2 для своего левого поддерева, но он еще не проверил свое правое поддерево, поэтому max(height(root.left), height(root.right)) должен ждать.
Процесс в основном такой же для правого поддерева {1}: если узел не является конечным узлом, он запрашивает у своих дочерних элементов их соответствующие высоты и принимает максимальное значение, добавляя 1 к самому себе,и сообщать родителю. В этом случае {6} сообщает о высоте от 1 до {5}, {5} сообщает о высоте от 2 до {3}, а {3} сообщает о высоте от 3 до {1}. Наконец, {1} может вычислить max(2, 3) и добавить 1 для его собственной высоты, возвращая конечному результату 4 для вызывающего абонента.
Если все это немного абстрактно, вы всегда можете использовать инструментрекурсивный вызов для добавления параметра depth и вывода его статуса.
from collections import namedtuple
Node = namedtuple("Node", "data left right")
def height(root, depth=0):
if root:
print(" " * depth + f"{{{root.data}}} asking children...")
left_height = height(root.left, depth + 4)
right_height = height(root.right, depth + 4)
ret = max(left_height, right_height) + 1
print(" " * depth + f"{{{root.data}}} reporting max({left_height}, {right_height}) + 1 = {ret}")
return ret
print(" " * depth + "None returning 0")
return 0
if __name__ == "__main__":
""" 1
/ \
2 3
\ /
4 5
\
6
"""
root = Node(
1,
Node(
2,
None,
Node(4, None, None)
),
Node(
3,
Node(
5,
None,
Node(6, None, None)
),
None
)
)
print(height(root)) # => 4
Вывод:
{1} asking children...
{2} asking children...
None returning 0
{4} asking children...
None returning 0
None returning 0
{4} reporting max(0, 0) + 1 = 1
{2} reporting max(0, 1) + 1 = 2
{3} asking children...
{5} asking children...
None returning 0
{6} asking children...
None returning 0
None returning 0
{6} reporting max(0, 0) + 1 = 1
{5} reporting max(0, 1) + 1 = 2
None returning 0
{3} reporting max(2, 0) + 1 = 3
{1} reporting max(2, 3) + 1 = 4
4