Блог

Не уверен, как это работает…

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

  def find_diameter(self, root):
    self.calculate_height(root)
    return self.treeDiameter

  def calculate_height(self, currentNode):
    if currentNode is None:
      return 0

    leftTreeDiameter = self.calculate_height(currentNode.left)
    rightTreeDiameter = self.calculate_height(currentNode.right)

    diameter = leftTreeDiameter   rightTreeDiameter   1
    self.treeDiameter = max(self.treeDiameter, diameter)

    return max(leftTreeDiameter, rightTreeDiameter)   1
 

Приведенный выше код работает для получения максимального диаметра двоичного дерева, но я не понимаю последнюю строку calculate_height . Зачем нам нужно возвращать max(leftTreeDiameter, rightTreeDiameter) 1

Я, очевидно, этого не понимаю, но что я знаю, так это то, что для каждого currentNode мы будем продолжать спускаться по левой стороне дерева и аналогично затем делать то же самое для правой. Если мы закончили без узла (то есть прямо перед тем, как мы были на конечном узле), тогда мы возвращаем 0, поскольку мы не хотим добавлять 1 для узла, который не существует.

Единственное место, которое, кажется, добавляет что-либо, кроме 0, — это последняя строка кода, calculate_height потому что, хотя мы добавляем leftTreeDiameter rightTreeDiameter 1 , чтобы получить общий диаметр, это возможно только из-за return 0 и return max(leftTreeDiameter, rightTreeDiameter) 1 правильно?

Кроме того, я не понимаю, почему можно назначить self.calculate_height(currentNode.left) leftTreeDiameter . Я имею в виду, что я думал, что мне понадобится что-то вроде…

 def calculate_left_height(self, currentNode, height=0):
  if currentNode is None:
    return 0

  self.calculate_height(currentNode.left, height   1)
  
  return height
 

где мы просто добавляем 1 к высоте каждый раз. В этом случае вместо того, чтобы делать что-то вроде leftTreeDiameter = self.calculate_height(currentNode.left) , я просто передаю в качестве аргумента height 1 каждый раз, когда мы видим узел.

но если я сделаю это, мне понадобится отдельный метод только для вычисления правильной высоты, и в моем find_diameter методе потребуется рекурсивный вызов find_diameter с обоими root.left , а также с root.right .

Где моя логика неверна и как это calculate_height работает на самом деле. Я думаю, у меня возникли проблемы, пытаясь понять, как отслеживать стек?

Имена, используемые в этом коде, сбивают с толку: leftTreeDiameter и rightTreeDiameter не диаметры, а высоты.

Во-вторых, функция calculate_height имеет побочные эффекты, что не очень приятно. С одной стороны, он возвращает высоту и одновременно присваивает диаметр. Это сбивает с толку. Многие программисты на Python предпочли бы, чтобы функция была чистой и просто возвращала что-то, ничего не изменяя. Или, альтернативно, функция может только изменять некоторое состояние и не возвращать его. Выполнение обоих может сбить с толку.

Кроме того, сбивает с толку то, что, хотя класс вызывается TreeNode , его find_diameter метод по-прежнему требует node в качестве аргумента. Это противоречит интуиции. Мы ожидаем, что метод будет использоваться в self качестве узла для действия, а не аргумента.

Но давайте просто переименуем переменные и добавим несколько комментариев:

 leftHeight = self.calculate_height(currentNode.left)
rightHeight = self.calculate_height(currentNode.right)

# What is the size of the longest path from leaf-to-leaf 
#   whose top node is the current node?
diameter = leftHeight   rightHeight   1
# Is this path longer than the longest path that we
#   had found so far? If so, take this one.
self.treeDiameter = max(self.treeDiameter, diameter)
# The height of the tree rooted at the current node
#   is the height of the highest childtree (either left or right), 
#   with one added to account for the current node
return max(leftHeight, rightHeight)   1
 

Это должно быть ясно, но поймите, что self в этом процессе всегда есть экземпляр, для которого find_diameter вызывается метод, и на самом деле он не играет роли фактического узла, поскольку корень передается в качестве аргумента. Таким образом, повторное присвоение self.treeDiameter всегда одному и тому же свойству. Это свойство создается не на каждом узле… только на узле, на котором вы вызываете find_diameter .

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