這次我們來解一道二元樹的題目：Diameter of Binary Tree，這道題目的關鍵在於找到二元樹中兩個節點之間的最長路徑，這段路徑稱為「直徑」。

接下來我會詳細講解每一步的解法與思路，幫助你更好理解這個問題。

前言

今天我們要挑戰的是 Diameter of Binary Tree（二元樹的直徑）。
二元樹的「直徑」就是樹中兩個節點之間的最長路徑，這條路徑可以不經過根節點。
這題看起來像是在玩迷宮遊戲，尋找最長的路徑～讓我們一步步來解這個問題吧！

題目 Diameter of Binary Tree

難度：Easy

題目描述：

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

給定一棵二元樹的根節點 root，返回樹的直徑（即兩個節點之間的最長路徑長度）。
這條路徑可能經過根節點，也可能不經過根節點。

路徑的長度由兩個節點之間的邊數來表示。

範例 1：

輸入： root = [1,2,3,4,5]

輸出： 3

解釋： 二元樹的直徑長度是 3，路徑是 [4,2,1,3] 或 [5,2,1,3]。

範例 2：

輸入： root = [1,2]

輸出： 1

思路

這道題目主要考察如何計算樹的深度，然後找到從左子樹到右子樹經過根節點的最長路徑。

如何思考這道題？

1. 遞迴遍歷樹的深度：每個節點的「深度」是它的左子樹和右子樹的最大深度+1（即到根節點的高度）。

2. 計算路徑長度：對於每個節點，該節點的「直徑」是它的左子樹深度和右子樹深度之和。
   通過比較所有節點的直徑，我們可以找到整棵樹的最大直徑。

3. 為什麼不只考慮根節點？：直徑可能經過任意節點，因此需要檢查每個節點的最大深度和路徑。

詳細步驟

1. 用遞迴方法計算每個節點的深度：這是解決樹問題的常用技巧。
   我們對每個節點的左子樹和右子樹分別計算深度，然後返回最大值。

2. 計算每個節點的直徑：當遞迴計算深度時，我們可以同時計算每個節點的直徑，這就是該節點的左子樹深度加上右子樹深度。

3. 更新最大直徑：我們在每次遞迴中更新當前的最大直徑，最後返回這個最大值。

實作

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

function diameterOfBinaryTree(root: TreeNode | null): number {
    let diameter = 0;

    // 遞迴函數計算節點的深度，同時更新直徑
    function depth(node: TreeNode | null): number {
        if (node === null) return 0; // 如果節點為空，深度為0

        // 計算左右子樹的深度
        const leftDepth = depth(node.left);
        const rightDepth = depth(node.right);

        // 更新直徑，當前節點的直徑為左子樹深度 + 右子樹深度
        diameter = Math.max(diameter, leftDepth + rightDepth);

        // 返回當前節點的深度
        return Math.max(leftDepth, rightDepth) + 1;
    }

    depth(root); // 從根節點開始遞迴計算
    return diameter; // 返回計算出的最大直徑
}

解題心法

1. 遞迴計算深度：
   我們使用遞迴來遍歷每個節點，對於每個節點，我們分別計算其左子樹和右子樹的深度。當我們拿到某個節點的左右子樹深度後，可以計算出以該節點為中心的直徑。

2. 更新最大直徑：
   每次計算出當前節點的直徑（左子樹深度 + 右子樹深度），我們就更新全局的最大直徑。這樣一旦有更大的直徑出現，我們就會更新最大值。

3. 處理空節點：
   如果某個節點為空，深度自然是 0，所以我們在遞迴的基礎條件中將空節點的深度設為 0。

4. 返回最大直徑：
   遞迴結束後，我們的全局變數 diameter 中就會存儲著最長的路徑長度（直徑），這就是我們最終要返回的值。

過程思路

• 第一步：我們需要定義一個全局變數 diameter，用來儲存二元樹的最大直徑。

• 第二步：我們設計一個遞迴函數 depth()，這個函數的作用是計算某個節點的深度（即到葉節點的最長路徑）。
  當 depth() 遞迴時，我們同時會計算該節點的直徑，並更新全局的最大直徑。

• 第三步：在遞迴的過程中，我們會不斷計算每個節點的左子樹和右子樹的深度，並用它們來計算直徑。
  當某個節點的直徑大於當前最大值時，我們更新最大直徑。

• 第四步：最終當遞迴結束後，我們的全局變數 diameter 就會存儲著二元樹中最大的直徑，我們只需返回這個變數即可。

本次要點：

• 利用遞迴來計算每個節點的深度，並同時計算直徑。
• 每個節點的直徑是其左子樹和右子樹深度之和。
• 使用全局變數來追蹤最大直徑，最終返回該值。

這道題是不是看起來像在探索一個迷宮呢？
透過計算每個節點的深度，我們找到了最長的那條路徑！下次再來一起挑戰更多有趣的題目吧！