二叉树的直径
我正在研究一个著名的问题，叫做二叉树的直径。我知道这里已经讨论过很多次了(Diameter of Binary Tree)，但解释似乎并不正确。特别是，单个节点树应该返回0，而不是1(我从Leetcode自己的检查器检查过)。无论如何，以下是问题陈述：
给定一棵二叉树，你需要计算这棵树的直径的长度。二叉树的直径是树中任意两个节点之间最长路径的长度。此路径可能通过根，也可能不通过。
答案分别为0、1和5。乍一看，计算左子树的边数和右子树的边数应该会得到答案。
因此，我从后序递归(自下而上)开始：
max_diameter = 0
def getDiameter(node):
if node is NULL:
return 0
left_diameter = getDiameter(node.left)
right_diameter = getDiameter(node.right)
max_diameter = max(left + right, max_diameter)到目前一切尚好。但是代码不起作用，我很难理解一些解决方案。例如：
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
def depth(p):
if not p: return 0
left, right = depth(p.left), depth(p.right)
self.ans = max(self.ans, left+right)
return 1 + max(left, right)
depth(root)
return self.ans为什么要比较左子树和右子树呢？为什么是+ 1？还有，有人说要找到高度，有人说要找到深度。这很令人困惑，我觉得人们只是在那里抛出术语。任何澄清都是有帮助的。
回答 2
Stack Overflow用户
发布于 2019-03-22 06:57:43
最长的路径总是从一个叶向上到达一个节点，然后再向下返回到另一个叶。从节点上看，这条路径的长度是左子树的最大深度和右子树的最大深度之和。
我们不能只将其应用于根节点，正如您的第三个示例所示，该节点可能位于树中的任何位置。因此，您必须测试所有节点并获得最大解：
diameter (Leaf) = 0
diameter (Node l r) = max(diameter l, diameter r, depth l + depth r)
depth (Leaf) = 0
depth (Node l r) = 1 + max(depth l, depth r)您找到的解决方案递归地计算所有节点上的深度，并在此过程中还更新self.ans插槽中的最大直径。
Stack Overflow用户
发布于 2020-04-12 14:08:21
在每个节点，你需要知道你的子节点的深度来计算树的直径，直径基本上是从你左子节点的最深节点到右子节点的最深节点的距离。
关于你的第二个代码(这个问题的解决方案)，我们正在计算每个节点的深度，同时跟踪到目前为止我们在每个探索的节点上看到的最长路径。这是一个更多的评论风格：
def diameterOfBinaryTree(self, root):
self.longest = 0
def depth(node):
if not node:
return 0
left_depth = depth(node.left)
right_depth = depth(node.right)
# A path is longest if we add depths from both sides
# Overall Longest is maximum of what we have seen so far and this path
self.longest = max(self.longest, left_depth+right_depth)
# Depth at this node is maximum of either of our children +1 (our own node)
return max(left_depth, right_depth) + 1
# Calculating depth, meanwhile tracking the longest path in self.longest
depth(root)
return self.longesthttps://stackoverflow.com/questions/55289654
复制相似问题
腾讯云开发者
