二叉树的直径
二叉树的直径
提问于 2019-03-22 05:38:57
我正在研究一个著名的问题，叫做二叉树的直径。我知道这里已经讨论过很多次了(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？还有，有人说要找到高度，有人说要找到深度。这很令人困惑，我觉得人们只是在那里抛出术语。任何澄清都是有帮助的。
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.longest页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55289654
复制相关文章
相似问题
腾讯云开发者
