0

我正在研究一个著名的问题，称为二叉树的直径。我知道这已经讨论了很多次（二叉树的直径），但解释似乎不正确。特别是，单个节点树应该返回 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？还有，有人说找高度，有人说找深度。这令人困惑，我觉得人们只是在抛出术语......任何澄清都是有帮助的。

4

2 回答 2

0

在每个节点处，您需要知道孩子的深度以从中计算树的直径，其中直径基本上是您从左孩子的最深节点到右孩子的最深节点可以走多远。

参考您的第二个代码（此问题的解决方案），我们正在计算每个节点的深度，同时跟踪我们迄今为止在每个已探索节点上看到的最长路径。这是它的更多评论风格：

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
于 2020-04-12T06:08:20.967 回答
0

最长的路径总是从一个叶子到一个节点，然后再回到另一个叶子。从节点上看，这条路径的长度为左子树的最大深度和右子树的最大深度之和。

我们不能只将其应用于根节点，因为您的第三个示例显示该节点可能位于树中的任何位置。所以你必须测试所有节点并获得最大的解决方案：

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槽中的最大直径。

于 2019-03-21T22:57:42.743 回答