一、學習目標

• 熟悉樹的基本觀念：根、深度、高度、父子關係、直徑（diameter）。
• 會用 DFS/BFS 在 O(n) 內處理常見樹問題（最長路徑、節點最遠距離、樹高）。
• 掌握「兩次 BFS/DFS 求直徑」與「從直徑兩端作距離」的萬用套路。
• 熟悉二元樹版本：最大深度、直徑（遞迴回傳高度、同時更新答案）。

二、觀念說明

• 樹 = 無環連通圖。對於 n 個點、n-1 條邊。
• 樹直徑：樹上最長簡單路徑的長度（邊數）。
  套路：
  1. 任選一點 s，BFS/DFS 找到最遠點 a；
  2. 從 a 再 BFS/DFS 找到最遠點 b，距離 dist(a,b) 即直徑長度。
• 節點的「最遠距離」（eccentricity）：對每個節點 v，答案 = max(dist_a[v], dist_b[v])（a,b 為直徑兩端）。
• 二元樹深度/高度：
  • maxDepth(root) = 1 + max(depth(left), depth(right))。
  • 直徑（節點間邊數）：在遞迴回傳「高度」同時更新全域 ans = max(ans, leftHeight + rightHeight)。

三、CSES實戰演練

題目1:Tree Diameter

原題:
https://cses.fi/problemset/task/1131

題意:
給一棵 n 點樹（無根、無權），輸出樹的直徑長度（兩點間最長路徑的邊數）。

解題思路:

• 兩次 BFS/DFS：
  • 從任意點（如 1）找最遠點 a；
  • 從 a 再找最遠點 b，dist[a][b] 即直徑長度。
• 時間複雜度 O(n)。

#include <bits/stdc++.h>
using namespace std;

pair<int,int> farthest(int src, const vector<vector<int>>& g){
    int n = g.size() - 1;
    vector<int> dist(n+1, -1);
    queue<int> q;
    dist[src] = 0; q.push(src);
    int best = src;
    while(!q.empty()){
        int u = q.front(); q.pop();
        if(dist[u] > dist[best]) best = u;
        for(int v: g[u]){
            if(dist[v] == -1){
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return {best, dist[best]};
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<vector<int>> g(n+1);
    for(int i=0;i<n-1;i++){
        int u,v; cin>>u>>v;
        g[u].push_back(v); g[v].push_back(u);
    }
    auto [a,_] = farthest(1, g);
    auto [b,diam] = farthest(a, g);
    cout << diam << "\n";
    return 0;
}

題目2:Tree Distances I

原題:
https://cses.fi/problemset/task/1132

題意:
給一棵 n 點樹，對每個節點 v，輸出它到樹上最遠節點的距離。

解題思路:

• 先用上題套路找直徑端點 a, b。
• 再各做一次 BFS/DFS，得到 distA[] 與 distB[]。
• 對每個節點 v，答案 ans[v] = max(distA[v], distB[v])。
• 複雜度 O(n)。

#include <bits/stdc++.h>
using namespace std;

vector<int> bfs(int src, const vector<vector<int>>& g){
    int n = g.size()-1;
    vector<int> dist(n+1, -1);
    queue<int> q; dist[src]=0; q.push(src);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int v: g[u]) if(dist[v]==-1){
            dist[v]=dist[u]+1; q.push(v);
        }
    }
    return dist;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<vector<int>> g(n+1);
    for(int i=0;i<n-1;i++){
        int u,v; cin>>u>>v;
        g[u].push_back(v); g[v].push_back(u);
    }
    // 找直徑兩端
    auto d1 = bfs(1, g);
    int a = 1;
    for(int i=1;i<=n;i++) if(d1[i] > d1[a]) a = i;
    auto dA = bfs(a, g);
    int b = a;
    for(int i=1;i<=n;i++) if(dA[i] > dA[b]) b = i;
    auto dB = bfs(b, g);

    for(int i=1;i<=n;i++){
        cout << max(dA[i], dB[i]) << (i==n?'\n':' ');
    }
    return 0;
}

四、Leetcode實戰演練

題目1:Maximum Depth of Binary Tree

原題:
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

題意:
給二元樹根節點 root，回傳樹的最大深度（根到最遠葉子的節點數）。

解題思路:

• 標準 DFS：depth(node) = 1 + max(depth(left), depth(right))；空節點回 0。
• 也可 BFS 一層層數。

/**
 * Definition for a binary tree node.
 * struct TreeNode { int val; TreeNode *left; TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

題目2:Diameter of Binary Tree

原題:
https://leetcode.com/problems/diameter-of-binary-tree/description/

題意:
給二元樹根節點 root，回傳直徑長度（任兩節點間最長路徑的邊數）。

解題思路:

• 遞迴函式回傳「該節點為根的高度」，同時更新全域 ans：
  ans = max(ans, leftHeight + rightHeight)。
• 最後回傳 ans 即為直徑（邊數）。
• 複雜度 O(n)。

class Solution {
    int best = 0;
    int height(TreeNode* node){
        if(!node) return 0;
        int L = height(node->left);
        int R = height(node->right);
        best = max(best, L + R);   // 經過此節點的路徑
        return 1 + max(L, R);
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return best;
    }
};