不确定此代码如何获得树的直径

Question

我不确定这个解决方案是如何工作的

给定一棵二叉树，求其直径的长度。树的直径是任意两个叶节点之间最长路径上的节点数。一棵树的直径可能穿过根，也可能不穿过根

注意：您始终可以假设给定树中至少有两个叶节点

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


class TreeDiameter:

  def __init__(self):
    self.treeDiameter = 0

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

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

    leftTreeHeight = self.calculate_height(currentNode.left)
    rightTreeHeight = self.calculate_height(currentNode.right)

    # if the current node doesn't have a left or right subtree, we can't have
    # a path passing through it, since we need a leaf node on each side
    if leftTreeHeight is not None and rightTreeHeight is not None:

      # diameter at the current node will be equal to the height of left subtree +
      # the height of right sub-trees + '1' for the current node
      diameter = leftTreeHeight + rightTreeHeight + 1

      # update the global tree diameter
      self.treeDiameter = max(self.treeDiameter, diameter)

    # height of the current node will be equal to the maximum of the heights of
    # left or right subtrees plus '1' for the current node
    return max(leftTreeHeight, rightTreeHeight) + 1


def main():
  treeDiameter = TreeDiameter()
  root = TreeNode(1)
  root.left = TreeNode(2)
  root.right = TreeNode(3)
  root.left.left = TreeNode(4)
  root.right.left = TreeNode(5)
  root.right.right = TreeNode(6)
  print("Tree Diameter: " + str(treeDiameter.find_diameter(root)))
  root.left.left = None
  root.right.left.left = TreeNode(7)
  root.right.left.right = TreeNode(8)
  root.right.right.left = TreeNode(9)
  root.right.left.right.left = TreeNode(10)
  root.right.right.left.left = TreeNode(11)
  print("Tree Diameter: " + str(treeDiameter.find_diameter(root)))


main()

我的第一个想法是每次看到左节点时添加1，每次看到右节点时添加1，但是从上面的代码中我看到解决方案只是将递归调用分配给leftTreeHeight和rightTreeHeight。然后我们检查左右两侧是否都有叶节点，因为如果没有，那么由于树直径的定义，我们将无法添加任何内容

从这里我看到的是，也许一旦我们开始跳出堆栈，我们就会更新我们的值，但我很难理解这一点。我调试了这段代码，看看它是如何工作的，但我很难理解

Answer 1

该代码可以工作，但我认为实现是不正确的。因为：

if currentNode is None:
      return 0

此代码表示，如果节点为“null”，则表示高度为0。好啊单个节点的高度如何。这也是0。假设您执行了递归调用并到达树的叶子：

当您达到“null”时，它将返回-1。当你到达节点8时，它会问它的左右两侧“你的身高是多少”，然后它们会返回(-1)+(-1)=-2。 我们知道单个节点的高度为0，所以节点8的高度将为0。目前node8从他的呼叫中接收-2。我们说，要让数学起作用

height_node8=(-1)+(-1) + 2

所以这个声明

  ` diameter = leftTreeHeight + rightTreeHeight + 1  `

应该是

  diameter = leftTreeHeight + rightTreeHeight + 2 

及

  if currentNode is None:
      return -1

我希望这是有道理的：

Answer 2

对于每个节点，您可以计算“节点局部”直径，这是从一片叶子到上、穿过节点到下到另一片叶子的最长距离。树的直径是所有节点局部直径的最大值

本质上，calculate_height以自下而上的方式计算每个节点的节点局部直径，因此所有节点局部直径都是计算树高的副作用

---

术语“直径”来自这样一个事实，即您可以选择树中的任何节点作为“根”，因此直径为d的树可以被重新解释为通过根的最长上下路径与直径相同的树，从而使根在某种程度上类似于树的“中心”（尽管根与两片叶子的距离不一定相同）