概述#

Tree 與 Graph 的題目往往是面試中最棘手的部分。與線性資料結構（如陣列、linked list）的搜尋相比，樹的搜尋更為複雜，且最差情況與平均情況的時間複雜度可能差距極大，需要全面評估。能從零開始實作 tree 或 graph，是面試的必備能力。

本章的部分術語在不同教科書中定義略有不同。若與面試官的定義有出入，應主動釐清。

Types of Trees#

Tree 是由節點（node）組成的資料結構，可以用遞迴方式理解：

• 每棵 tree 有一個 root node（根節點）
• root node 有零個或多個 child nodes（子節點）
• 每個 child node 同樣有零個或多個子節點，依此類推

Tree 中不能有環（cycle）。節點可以按任何順序排列，值可以是任何資料型別，也可以有或沒有指向父節點的連結。

class Node {
    public String name;
    public Node[] children;
}

Trees vs. Binary Trees#

Binary Tree（二元樹） 是每個節點最多有兩個子節點的 tree。並非所有 tree 都是 binary tree——例如每個節點有三個子節點的稱為三元樹（ternary tree）。

沒有子節點的節點稱為葉節點（leaf node）。

Binary Tree vs. Binary Search Tree#

Binary Search Tree（二元搜尋樹，BST） 是每個節點都滿足以下性質的 binary tree：

所有左側後代節點 <= n < 所有右側後代節點

此條件必須對每一個節點 n 都成立，而不只是直接的子節點。

面試時，許多人看到 tree 題目會直接假設是 BST。務必先確認——題目說的可能只是普通的 binary tree。

Balanced vs. Unbalanced#

平衡（balanced） 不代表左右子樹大小完全相同。它的實際意義是：平衡到足以確保 insert 和 find 操作為 O(log n)。兩種常見的平衡樹：

• Red-Black Tree（紅黑樹）
• AVL Tree

Complete Binary Trees#

Complete Binary Tree（完全二元樹） 是除了最後一層外，每一層都完全填滿，且最後一層的節點從左到右填入。

Full Binary Trees#

Full Binary Tree（完整二元樹） 是每個節點恰好有 0 或 2 個子節點，不存在只有 1 個子節點的節點。

Perfect Binary Trees#

Perfect Binary Tree（完美二元樹） 既是 complete 又是 full 的 binary tree。所有葉節點都在同一層，且這一層的節點數量最多。

Perfect binary tree 在面試和現實中都很罕見——它必須恰好有 2^k - 1 個節點（k 為層數）。不要假設一棵 binary tree 是 perfect 的。

Binary Tree Traversal#

面試前應熟練掌握三種遍歷方式，其中最常見的是 In-Order Traversal。

In-Order Traversal（中序遍歷）#

順序：左子樹 → 當前節點 → 右子樹

void inOrderTraversal(TreeNode node) {
    if (node != null) {
        inOrderTraversal(node.left);
        visit(node);
        inOrderTraversal(node.right);
    }
}

在 BST 上執行中序遍歷，會以遞增順序訪問所有節點。

Pre-Order Traversal（前序遍歷）#

順序：當前節點 → 左子樹 → 右子樹

void preOrderTraversal(TreeNode node) {
    if (node != null) {
        visit(node);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

前序遍歷中，root 永遠是第一個被訪問的節點。

Post-Order Traversal（後序遍歷）#

順序：左子樹 → 右子樹 → 當前節點

void postOrderTraversal(TreeNode node) {
    if (node != null) {
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        visit(node);
    }
}

後序遍歷中，root 永遠是最後一個被訪問的節點。

Binary Heaps (Min-Heaps and Max-Heaps)#

此處以 Min-Heap 為主說明（Max-Heap 概念相同，只是元素為遞減順序）。

Min-Heap 是一個 complete binary tree，其中每個節點的值都小於或等於其子節點的值。因此，root 是整棵樹中最小的元素。

Insert（插入）#

1. 將新元素插入樹的最底層最右側（維持 complete tree 性質）
2. 不斷與父節點比較，若比父節點小則交換（bubble up）
3. 重複直到找到正確位置

此操作時間複雜度為 O(log n)。

Extract Minimum（取出最小值）#

1. 最小值永遠在 root
2. 移除 root，將最底層最右側的節點移到 root
3. 不斷與子節點比較，若比其中一個子節點大則與較小的子節點交換（bubble down）
4. 重複直到恢復 min-heap 性質

此操作同樣為 O(log n)。

Tries (Prefix Trees)#

Trie（又稱 prefix tree）是一種 n-ary tree 的變體，每個節點儲存一個字元。從 root 到某個節點的路徑代表一個字串前綴。

• * 節點（又稱 null node）用來標記一個完整單字的結尾
• 一個節點的子節點數量介於 1 到 ALPHABET_SIZE + 1 之間（若使用 boolean flag 則為 0 到 ALPHABET_SIZE）

Trie 最常見的應用是儲存整個英語詞典，用於快速前綴查詢。Hash table 能查詢一個字串是否為有效單字，但無法判斷它是否為某個有效單字的前綴；Trie 則能做到。

Trie 查詢前綴的時間複雜度為 O(K)，K 為字串長度。這與 hash table 的查詢時間相同（hash table 實際上也需要讀取所有字元）。但在涉及大量前綴反覆查詢時，Trie 可以透過傳遞當前節點的引用來避免重複從 root 開始查找。

Graphs#

Tree 是 graph 的一種，但並非所有 graph 都是 tree。簡單來說，tree 是無環（acyclic）的連通圖（connected graph）。

Graph 是由節點（node/vertex）與邊（edge）組成的資料結構，具有以下特性：

• 有向圖（directed）vs. 無向圖（undirected）：有向邊如同單行道，無向邊如同雙向道路
• 連通圖（connected graph）：每對頂點之間都存在路徑
• 無環圖（acyclic graph）：圖中不存在環

圖的表示方式#

Adjacency List（相鄰串列） — 最常見的表示方式

每個頂點（或節點）儲存一個相鄰頂點的列表。在無向圖中，邊 (a, b) 會被儲存兩次。

class Graph {
    public Node[] nodes;
}

class Node {
    public String name;
    public Node[] children;
}

使用 Graph 類別是因為與 tree 不同，無法從單一節點到達所有節點。

也可以用陣列（或 hash table）的列表來儲存相鄰串列：

0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5

Adjacency Matrix（相鄰矩陣）

N×N 的 boolean 矩陣，matrix[i][j] 為 true 表示從節點 i 到節點 j 有邊。在無向圖中，矩陣會是對稱的；在有向圖中則不一定。

相鄰串列比相鄰矩陣更常用。在相鄰串列中，可以輕鬆遍歷一個節點的所有鄰居；而在相鄰矩陣中，必須遍歷所有節點才能找到鄰居，效率較低。

Graph Search#

圖的兩種最常見搜尋方式：Depth-First Search（DFS） 與 Breadth-First Search（BFS）。

Depth-First Search（DFS，深度優先搜尋）#

從起始節點出發，先完整探索一條分支，再移至下一條分支——先深後廣。

void search(Node root) {
    if (root == null) return;
    visit(root);
    root.visited = true;
    for (Node n : root.adjacent) {
        if (n.visited == false) {
            search(n);
        }
    }
}

前序遍歷等 tree traversal 是 DFS 的一種形式。在 graph 中實作 DFS 時，必須記錄節點是否已被訪問，否則可能陷入無限迴圈。

Breadth-First Search（BFS，廣度優先搜尋）#

從起始節點出發，先探索所有鄰居，再前往鄰居的鄰居——先廣後深。

void search(Node root) {
    Queue queue = new Queue();
    root.marked = true;
    queue.enqueue(root); // 加入 queue 尾端

    while (!queue.isEmpty()) {
        Node r = queue.dequeue(); // 從 queue 前端取出
        visit(r);
        foreach (Node n in r.adjacent) {
            if (n.marked == false) {
                n.marked = true;
                queue.enqueue(n);
            }
        }
    }
}

許多人誤以為 BFS 是遞迴的，但它不是。BFS 使用 queue（而非 call stack）來實作，這是記憶的關鍵。

DFS vs. BFS 的使用時機#

• 想訪問 graph 中的每個節點：DFS 或 BFS 皆可，但 DFS 的實作較簡單
• 尋找兩節點之間的最短路徑（或任意路徑）：BFS 通常更適合

以「在全球社交網路中尋找 Ash 到 Vanessa 的路徑」為例：DFS 可能需要遍歷幾乎所有人才能找到答案；BFS 則會優先搜尋 Ash 的朋友，若 Vanessa 是 Ash 的朋友或朋友的朋友，很快就能找到。

Bidirectional Search（雙向搜尋）#

雙向搜尋從 source 和 destination 兩端同時進行 BFS，當兩個搜尋的邊界相遇時，即找到路徑。

效率分析：假設每個節點最多有 k 個相鄰節點，最短路徑長度為 d：

• 傳統 BFS：需搜尋約 O(k^d) 個節點
• 雙向搜尋：兩端各搜尋約 k^(d/2) 個節點，共約 O(k^(d/2)) 個節點

由於 k^(d/2) * k^(d/2) = k^d，雙向搜尋實際上比傳統 BFS 快了 k^(d/2) 倍，效益非常顯著。

面試題目列表#