Каково на самом деле определение корня (входа) дерева

Я как бы новичок в структуре даты.

В некоторых задачах Leetcode вводятся следующие данные: root = [1,2,3,4,5, null, 6,7, null], а тип корня - TreeNode, который выглядит как один узел, как показано ниже.

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

Но здесь явно указан список: root = [1,2,3,4,5, null, 6,7, null]

Когда я создаю рекурсивную функцию, и она получает корень в качестве входных данных и, возможно, возвращает целое число, начинает ли она автоматически работать с первым элементом в этом дереве, даже если корень здесь является деревом элементов? Мне кажется, что многие такие функции вызывают root и используют его как единственную переменную (или узел) вместо всего дерева, что иногда меня смущает. Например

def afunction(self, root: TreeNode) -> int:
    
        queu = [root]
        maxDepth = float('-inf')
        result = 0
        .....

Корень здесь кажется узлом, который на самом деле не содержит значения? А как его сохранить как queu = [root]?


person JWT    schedule 23.01.2021    source источник
comment
Этот список структурирован как двоичная куча (дерево). Подробнее см. Здесь: en.wikipedia.org/wiki/Heap_(data_structure)   -  person Alain T.    schedule 24.01.2021


Ответы (1)


Список, вероятно, представляет собой дерево, в котором узел с индексом i имеет двух дочерних узлов с индексами 2*i + 1 и 2*i + 2. Ваш данный список затем представляет собой дерево

                      1
                    (i=0)
                    /   \
                  2      3
                (i=1)  (i=2)
                /   \      \
              4      5      6 
            (i=3)  (i=4)  (i=6)
            /
           7
         (i=7) 

Согласно этой интерпретации, нет особой разницы между корнем и деревом, укорененным в корневом узле. Однако обратите внимание, что поддерево - это не отдельный фрагмент дерева, и объединение двух деревьев под одним корневым узлом не соответствует простому объединению списков.

person chepner    schedule 23.01.2021