題目

難度：★★☆☆☆
類型：二叉樹

給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結(jié)點(diǎn)路徑長度中的最大值。這條路徑可能穿過根結(jié)點(diǎn)。

注意：兩結(jié)點(diǎn)之間的路徑長度是以它們之間邊的數(shù)目表示。

示例

給定二叉樹

          1
         / \
        2   3
       / \
      4   5

返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。

解答

class Solution:

    def diameterOfBinaryTree(self, root) -> int:
        if not root:
            return 0
        res = []
        self.dfs(root, res)
        return max(res) - 1

    def dfs(self, root, res):
        if not root:
            return 0
        left = self.dfs(root.left, res)
        right = self.dfs(root.right, res)
        res.append(left + right + 1)
        return max(left, right) + 1

如有疑問或建議，歡迎評論區(qū)留言~