軟體工程師職涯升級計畫啟動！立即預約職涯諮詢、履歷健檢或模擬面試👈，為您的加薪做好準備！
樹（Tree）是一種常見且重要的非線性資料結構，經常出現在程式設計面試題目中。你可以將它想像成一個倒置的家族族譜，用來組織與儲存層級化資料。它的核心特徵如下：
- 唯一的根節點 (Root)：整棵樹的起點，且只存在一個。
- 單一父節點 (Single Parent)：除了根節點外，每個節點都僅有一個父節點。
- 無環結構 (No Cycles)：任意兩節點間只有一條唯一路徑，不會形成循環。
以下這兩種資料並不屬於 tree
常見術語
在面試中，樹的相關術語經常被問到，以下是基本概念：- 節點 (Node)：樹中的每個資料元素。
- 根 (Root)：位於最上層的節點。
- 葉節點 (Leaf)：沒有子節點的節點，代表分支的終點。
- 父節點 (Parent) 與 子節點 (Child)：層級關係中，指向下層的為父節點，被指向的為子節點。
- 深度 (Depth)：從根節點到某一節點的邊數，根節點深度為 0。
- 高度 (Height)：從某一節點到最遠葉節點的邊數，葉節點高度為 0。
樹的建構：程式中的表示方式
在程式設計中，樹的節點通常以**類別（Class）或物件（Object）**來定義。以下是 JavaScript 的簡單實作範例：
class TreeNode {
constructor(val) {
this.val = val;
this.left = null; // 左子節點
this.right = null; // 右子節點
}
}
在面試中，最常遇到的樹種類包含：
- 二元樹 (Binary Tree)：每個節點最多有兩個子節點（左、右）。
- 二元搜尋樹 (Binary Search Tree, BST)：在二元樹的基礎上增加排序規則：
- 左子節點值 < 父節點值
- 右子節點值 > 父節點值
這個特性讓搜尋、插入與刪除的效率大幅提升。
樹的遍歷（Traversal）
遍歷樹是面試常見的必考題，主要分為兩大類：
1. 深度優先搜尋（DFS, Depth-First Search）
DFS 的思路是「一路走到底，再回頭」，可以透過遞迴或堆疊 (Stack) 來實作。
常見的三種走訪方式：
- 前序遍歷 (Pre-order)：中 → 左 → 右
- 中序遍歷 (In-order)：左 → 中 → 右
對 BST 進行中序遍歷，可得到排序後的數列。
- 後序遍歷 (Post-order)：左 → 右 → 中
遞迴版本
function preorder(root) {
if (!root) return [];
return [root.val, ...preorder(root.left), ...preorder(root.right)];
}
function inorder(root) {
if (!root) return [];
return [...inorder(root.left), root.val, ...inorder(root.right)];
}
function postorder(root) {
if (!root) return [];
return [...postorder(root.left), ...postorder(root.right), root.val];
}
迭代版本
// 前序遍歷 (Pre-order)
function preorderIter(root) {
if (!root) return [];
const stack = [root], result = [];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}
// 中序遍歷 (In-order)
function inorderIter(root) {
const stack = [], result = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.push(current.val);
current = current.right;
}
return result;
}
// 後序遍歷 (Post-order)
function postorderIter(root) {
if (!root) return [];
const stack = [root], result = [];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return result.reverse();
}
複雜度分析
- 時間複雜度：O(n)，每個節點僅訪問一次。
- 空間複雜度：O(h)，其中 h 為樹的高度。最壞情況 O(n)，最佳情況（平衡樹） O(log n)。
2. 廣度優先搜尋（BFS, Breadth-First Search）
BFS 的思路是「逐層遍歷」，通常透過佇列 (Queue) 來實現。
JavaScript 實作
function bfs(root) {
if (!root) return [];
const queue = [root], result = [];
while (queue.length > 0) {
const node = queue.shift();
result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return result;
}
複雜度分析
- 時間複雜度：O(n)，每個節點訪問一次。
- 空間複雜度：O(w)，其中 w 為樹的最大寬度。最壞情況 O(n)。
二元樹（Binary Tree）
二元樹是一種特殊的樹狀結構，其中每個節點最多只能有兩個子節點，分別稱為左子節點（Left Child）與右子節點（Right Child）。這也是面試中最常出現的樹類型之一。
二元樹的種類
- 滿二元樹（Full Binary Tree）
每個節點要嘛沒有子節點，要嘛剛好有兩個子節點。 - 完全二元樹（Complete Binary Tree）
除了最後一層外，其他層的節點都是滿的，最後一層的節點集中在左側。 - 完美二元樹（Perfect Binary Tree）
一棵同時滿足「滿二元樹」與「完全二元樹」條件的二元樹，所有葉節點位於同一層。 - 二元搜尋樹（Binary Search Tree, BST）
在二元樹的基礎上增加排序規則： - 左子節點的值 < 父節點
- 右子節點的值 > 父節點
這讓 BST 在搜尋、插入與刪除時的效率更高。
二元樹的應用
- 搜尋與排序：BST 可在平均 O(log n) 的時間內完成搜尋。
- 堆積樹（Heap）：用於實作優先佇列（Priority Queue）。
- 表達式樹（Expression Tree）：常見於編譯器與運算解析。
範例程式碼（建構簡單的二元樹）
// 建立節點
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
/*
樹的結構：
1
/ \
2 3
/ \
4 5
*/
經典題目：Validate Binary Search Tree（LeetCode 98）
題目說明：判斷給定的二元樹是否為有效的 BST。
核心思路：在遍歷過程中，為每個節點設定「有效值範圍」。若節點值超出範圍，則違反 BST 規則。
JavaScript 解法
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function(root) {
function validate(node, min, max) {
if (!node) return true;
if ((min !== null && node.val <= min) || (max !== null && node.val >= max)) {
return false;
}
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
return validate(root, null, null);
};
總結
- DFS 適合需要完整遍歷樹結構或進行遞迴處理的情境。
- BFS 適合需要按層級搜尋、找最短路徑或最淺解答的情境。
- 時間複雜度：DFS 與 BFS 都是 O(n)。
- 空間複雜度：DFS 為 O(h)，BFS 為 O(w)。
👉 熟悉這些基本概念與程式碼實作，能幫助你在演算法面試中更快進入狀況，應對各種樹的題目。
