Алгоритм Python для определения максимального пути в двоичном дереве не работает должным образом - PullRequest
Новая
       8

Алгоритм Python для определения максимального пути в двоичном дереве не работает должным образом

0 голосов
/ 19 января 2019

Я пытался написать алгоритм Python, который бы нашел максимальную сумму для пути целых чисел в двоичном дереве. Я думал, что самым простым способом сделать это будет рекурсивная функция, но, похоже, это не работает так, как я хотел. Как я мог бы пересмотреть эту функцию, чтобы она нашла абсолютный максимальный путь? Я могу подтвердить, что построение дерева пока работает нормально, потому что функция высоты, которую я написал для него, работала так, как задумано. 

class Node:
    def __init__(self, data):
        self.right = self.left = None
        self.data = data

class Solution:
    def insert(self, root, data):
        if not root:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left, data)
                root.left=cur
            else:
                cur=self.insert(root.right, data)
                root.right=cur
        return root

def get_height(self, root):
    if not root or root.left == root.right == None:
        return 0
    return 1 + max(self.get_height(root.left), self.get_height(root.right))

def get_max_sum(self, root):
    if not root:
        return 0
    return root.data + max(self.get_max_sum(root.left), self.get_max_sum(root.right))

Код IO: 

 nums = '''75
    95 64
    17 47 82
    18 35 87 10
    20 04 82 47 65
    19 01 23 75 03 34
    88 02 77 73 07 63 67
    99 65 04 28 06 16 70 92
    41 41 26 56 83 40 80 70 33
    41 48 72 33 47 32 37 16 94 29
    53 71 44 65 25 43 91 52 97 51 14
    70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
    63 66 04 68 89 53 67 30 73 16 69 87 40 31
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''.replace('\n', ' ')
    nums = tuple(map(int, nums.split(' ')))

    tree = Solution()
    root = None
    for i in nums:
        data = i
        root = tree.insert(root, data)

    height = tree.get_height(root)
    msum = tree.get_max_sum(root)
    print(height, msum)

1 Ответ

0 голосов
/ 19 января 2019

Этот код делает пару ошибочных предположений о проблеме, которые объясняют, почему она не работает так, как вы ожидаете.

  1. Входные данные представляют собой график , а не дерево .Глядя на этот пример ввода, где нас просят найти максимальный путь от корня к листу, 

       3
  7 4
 2 4 6
8 5 9 3

    Мы можем наблюдать следующие отношения между узлами: 

          3
     / \
    ↓   ↓
    7   4
   / \ / \
  ↓   ↓   ↓
  2   4   6
 / \ / \ / \
↓   ↓   ↓   ↓
8   5   9   3

    Поскольку каждыйВнутренний узел имеет двоих детей, вы должны (понятно) прийти к выводу, что это дерево.Но определение дерева таково, что у каждого ребенка не более одного родителя, поэтому у нас есть противоречие.На самом деле это направленный ациклический граф .

  2. Даже если это дерево, то его преобразование в BST кардинально меняет его структуру .Рассмотрим приведенный выше ввод еще раз.Выполнение алгоритма insert на нем приводит к следующей структуре бинарного дерева поиска : 

             3
        / \
       /   \
      /     \
     2       7
      \     / \
       3   4   8
          / \   \ 
         4   6   9
            /
           5

    Очевидно, что эта структура имеет мало общего с исходным вводом, и выполнение суммы максимального путиАлгоритм этой структуры даст 3 + 7 + 8 + 9 = 27, когда правильный ответ будет 3 + 7 + 4 + 9 = 23.

Я рекомендую переформулировать задачу как задачу о графике и исходя из этого.

...