二叉樹的直徑

題目來源：https://leetcode-cn.com/problems/diameter-of-binary-tree/

題目

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

示例 :

給定二叉樹

          1
         / \
        2   3
       / \     
      4   5    

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

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

解題思路

這里需要注意，二叉樹的直徑（最長路徑），有可能不經(jīng)過根節(jié)點。如下圖所示：

not_through_root

在這里，求二叉樹的直徑，即是求最長路徑。先判斷問題是否劃分為子問題。其實二叉樹路徑的問題，就是選擇問題：

          1
         / \
        2   3

1. [左] 2 - 1
2. [右] 3 - 1
3. [左中右]，2 - 1 - 3

根據(jù)上面的解析，那么現(xiàn)在將問題劃分為：

二叉樹最長路徑 = max{[左]，[右]，[左中右]}

其中 [左]，[右]，這兩種情況可以用遞歸進(jìn)行求解，因為葉子節(jié)點路徑為 0，往上走，例如 2 - 1，長度 + 1，也就是左右節(jié)點遞歸返回值 + 1。

而 [左中右] 這種情況情況，其實就是 左 + 右。

代碼實現(xiàn)

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 0

        def diameter_of_binary_tree(node, ans):
            # 遞歸出口
            if not node:
                return 0
            # 遞歸獲取左右兩種情況的直徑
            left_depth = diameter_of_binary_tree(node.left, self.ans)
            right_depth = diameter_of_binary_tree(node.right, self.ans)
            # 左中右的情況
            self.ans = max(self.ans, left_depth + right_depth)
            # 遞歸獲取的結(jié)果
            return max(left_depth, right_depth) + 1

        diameter_of_binary_tree(root, self.ans)
        return self.ans

實現(xiàn)結(jié)果

二叉樹的直徑--實現(xiàn)結(jié)果

以上就是使用遞歸的方法，解決《二叉樹的直徑》問題的主要內(nèi)容。

歡迎關(guān)注微信公眾號《書所集錄》