今天我們來加深對樹的遞迴思想的理解。

題目連結: 543. Diameter of Binary Tree

題目描述:給定一棵二元樹的根節點 root，返回樹的直徑。
樹的「直徑」是指 樹中任意兩個節點之間路徑的最大長度。這條路徑可能穿過也可能不穿過根節點。

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Python

解題思路:
這個問題的核心是找到「最長路徑」。要遍歷所有路徑，最自然的方法就是DFS。

對於樹中的任何一個節點，穿過它的最長路徑（直徑）是這個節點的「左子樹最大深度」+「右子樹最大深度」。

全局的最長路徑不一定會穿過根節點。它可能完全包含在左子樹中，或者完全包含在右子樹中。因此，我們需要遍歷樹中的每一個節點，計算穿過它的直徑，然後找出其中的最大值。

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        def dfs(node):
            if node ==None:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.ans = max(left+right,self.ans)
            return 1 + max(left,right)
        dfs(root)
        return self.ans

演算法分析:

• dfs(node)函式主要是做計算並返回以 node 為根的子樹的最大深度。次要是做計算深度的過程中，順便計算一下穿過 node 的直徑 ，並用它來更新全局的最大值。
• 使用self類別來讀取全局的值(self.ans)。
• self.ans = max(left+right,self.ans)left + right：這個表達式計算的正是穿過當前 node 節點的最長路徑（也就是這個節點的直徑），將當前節點的直徑與我們目前記錄的全局最大直徑 self.ans 比較，如果當前的更大，就更新它。
• return 1 + max(left,right)找出左右子樹中比較深的那一條路徑，再加上當前節點本身，就構成了以 node 為根的子樹的最大深度。
• dfs(root) 啟動了整個遞迴過程。這個過程會遍歷樹中的每一個節點，並在每一個節點上都執行一次「更新直徑」的檢查。
• 當 dfs(root) 執行完畢後， self.ans 中儲存的就必定是所有節點直徑中的最大值。

複雜度分析:

• 時間複雜度為 O(n)(我們使用 DFS 遍歷了樹中的每一個節點一次，n 是樹的總節點數)。
• 空間複雜度： O(n)。
  1. 空間消耗主要來自遞迴呼叫的堆疊深度，也就是樹的高度 n。
  2. 平均情況（樹是Avg Tree），空間複雜度是 O(log n)。
  3. 最壞情況（樹極度不平衡，退化成鏈結串列），空間複雜度是 O(n)。

有問題可以底下留言!
下回見!!