对二叉树的最大直径问题感到困惑

Question

不确定这是如何工作的...

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 中的最后一行。为什么我们需要returnmax(leftTreeDiameter, rightTreeDiameter) + 1

我显然不明白，但我知道的是，对于每个 currentNode，我们将继续沿着树的左侧向下走，然后类似地对右侧做同样的事情。如果我们最终没有节点（意思是在我们处于叶节点之前），那么我们 return 0 因为我们不想为不存在的节点添加 1。

除了 0 之外，唯一似乎要添加任何内容的地方是 calculate_height 中的最后一行代码，因为尽管我们添加 leftTreeDiameter + rightTreeDiameter + 1 以获得总直径，但这是唯一可能的，因为return 0 和 return max(leftTreeDiameter, rightTreeDiameter) + 1 正确吗？

此外，我很困惑为什么可以分配 leftTreeDiameter self.calculate_height(currentNode.left)。我的意思是我认为我需要类似...

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 方法中需要用 root.left 递归调用 find_diameter还有 root.right.

我的逻辑哪里错了，calculate_height 到底是怎么回事。我想我在尝试弄清楚如何跟踪堆栈时遇到了麻烦？

Answer 1

此代码中使用的名称令人困惑：leftTreeDiameter 和 rightTreeDiameter 不是直径，而是高度。

其次，函数calculate_height有副作用，不太好。一方面它returns一个高度，同时它分配一个直径。这令人困惑。许多 Python 编码人员更喜欢一个纯粹的函数，只是 return 一些东西，而不改变任何其他东西。或者，一个函数只能改变某些状态，不能 return。两者都做可能会造成混淆。

此外，令人困惑的是，尽管 class 被称为 TreeNode，但它的 find_diameter 方法仍然需要一个节点作为参数。这是违反直觉的。我们希望该方法将 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 的重复赋值总是对同一个 one 属性。这个属性不是在每个节点上创建的...只是在您调用 find_diameter.

的节点上创建的

我希望插入的评论已经阐明了该算法的工作原理。

注意：你自己关于创建 calculate_left_height 的想法不会这样做：它永远不会改变它作为参数接收的 height 的值，并最终 returning它。所以它 return 与它已经收到的值相同。这显然不会有太大作用...

对二叉树的最大直径问题感到困惑

confused about largest diameter of binary tree problem

python

algorithm

binary-tree

depth-first-search