《面試官問完，開AI回答》PHP 工程師的 LeetCode 刷題解構與模式化思考(一)

雜湊表 (Hash Table) 📚

雜湊表（Hash Table），又稱散列表，是一種根據鍵（key）直接訪問資料結構中儲存位置的資料結構。它透過雜湊函數將鍵映射到一個陣列的索引，實現快速的資料查找、插入和刪除。在 PHP 中，**關聯陣列（associative array）**就是雜湊表的一種實現。其平均時間複雜度可達 O(1)。

搭配例題１｜ (001) Two Sum

問題描述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

給定一個整數陣列 nums 和一個目標值 target，請找出陣列中兩個數字的索引，使得它們的和等於 target。

你可以假設每個輸入都只有一個確切的解，並且你不能重複使用同一個元素。

你可以按任何順序返回答案。

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

解題思路

本題的目標是找到兩個數的和為 target。

暴力解法 (Brute Force):

最直觀的方法是使用兩個巢狀迴圈，遍歷所有可能的兩數組合，檢查它們的和是否等於 target。

時間複雜度：O(n2)。

空間複雜度：O(1)。

使用雜湊表 (Hash Table) 優化:

為了將時間複雜度降低到 O(n)，我們可以使用雜湊表（在 PHP 中即關聯陣列）來儲存已經遍歷過的數字及其索引。

1. 遍歷陣列： 逐一遍歷 nums 陣列中的每個數字 num 及其索引 i。

2. 計算補數： 對於當前的 num，計算它需要的「補數」complement = target - num。

3. 查找補數： 檢查雜湊表中是否已經存在這個 complement。

   • 如果存在，這表示我們找到了這兩個數字。雜湊表中儲存的 complement 的索引，以及當前數字 num 的索引 i，就是我們要找的答案。

   • 如果不存在，則將當前的 num 及其索引 i 存入雜湊表中，以便後續數字可以查找它。

時間複雜度： O(n)。由於雜湊表的平均查找、插入操作為 O(1)，我們只需遍歷陣列一次。

空間複雜度： O(n)。在最壞情況下（沒有找到補數，直到遍歷完所有數字），雜湊表會儲存所有 n 個數字。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        // 創建一個雜湊表（PHP 中的關聯陣列）來儲存數字和它們的索引
        $hashMap = [];

        // 遍歷陣列中的每個數字及其索引
        foreach ($nums as $index => $num) {
            // 計算當前數字需要的補數
            $complement = $target - $num;

            // 檢查雜湊表中是否已經存在這個補數
            // array_key_exists 比 isset 更適合判斷鍵是否存在，因為它能區分 null 值
            if (array_key_exists($complement, $hashMap)) {
                // 如果存在，則表示找到了這兩個數字
                // 返回補數的索引（從 hashMap 中獲取）和當前數字的索引
                return [$hashMap[$complement], $index];
            }

            // 如果補數不存在，則將當前數字及其索引存入雜湊表，以供後續查找
            $hashMap[$num] = $index;
        }

        // 根據題目假設「每個輸入都只有一個確切的解」，所以理論上不會執行到這裡
        return []; 
    }
}
?>

---

搭配例題２｜ (242) Valid Anagram

問題描述

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

You may assume the string s contains only lowercase English letters.

給定兩個字串 s 和 t，如果 t 是 s 的字母異位詞，則返回 true，否則返回 false。

字母異位詞是透過重新排列另一個單字或短語的字母形成的單字或短語，通常恰好使用所有原始字母一次。

你可以假設字串 s 只包含小寫英文字母。

Example 1:

Input: s = "anagram", t = "nagaram"

Output: true

Example 2:

Input: s = "rat", t = "car"

Output: false

解題思路

判斷兩個字串是否為字母異位詞，核心思想是它們所包含的字元種類和數量必須完全相同。

方法一：排序 (Sorting)

將兩個字串各自轉換為字元陣列，然後對這兩個陣列進行排序。如果排序後的字元陣列相等，則它們互為字母異位詞。

時間複雜度：O(nlogn)，其中 n 是字串長度（受排序演算法影響）。

空間複雜度：O(n)，用於儲存字元陣列。

方法二：雜湊表或陣列計數 (Hash Table / Array Counting)

由於題目明確指出只包含小寫英文字母，我們可以利用一個固定大小的陣列（大小為 26）來充當雜湊表，記錄每個字元出現的次數。這比使用 PHP 的關聯陣列在特定情況下更有效率，因為避免了雜湊碰撞的開銷。

1. 長度檢查： 首先，如果兩個字串的長度不相等，它們絕對不可能是字母異位詞，直接返回 false。

2. 計數：

   • 建立一個大小為 26 的整數陣列，將所有元素初始化為 0。這個陣列的索引 0 對應字元 'a'，索引 1 對應 'b'，以此類推。

   • 遍歷字串 s，對於每個字元，將其對應的計數器加一。

   • 遍歷字串 t，對於每個字元，將其對應的計數器減一。

3. 驗證： 遍歷計數陣列。如果所有的計數器都為零，表示兩個字串的字元分佈完全相同，返回 true。否則，返回 false。

時間複雜度： O(n)，其中 n 是字串長度。我們遍歷了兩個字串一次，然後遍歷了固定大小的計數陣列。

空間複雜度： O(1)，因為計數陣列的大小是固定的 26。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param String $s
     * @param String $t
     * @return Boolean
     */
    function isAnagram($s, $t) {
        // 檢查兩個字串的長度是否相等
        if (strlen($s) !== strlen($t)) {
            return false;
        }

        // 創建一個大小為 26 的陣列來計數，索引 0 對應 'a'，1 對應 'b'，以此類推
        $charCount = array_fill(0, 26, 0);

        // 遍歷字串 s，增加對應字元的計數
        for ($i = 0; $i < strlen($s); $i++) {
            $charIndex = ord($s[$i]) - ord('a'); // 將字元轉換為 0-25 的索引
            $charCount[$charIndex]++;
        }

        // 遍歷字串 t，減少對應字元的計數
        for ($i = 0; $i < strlen($t); $i++) {
            $charIndex = ord($t[$i]) - ord('a'); // 將字元轉換為 0-25 的索引
            $charCount[$charIndex]--;
        }

        // 檢查計數陣列中是否有非零值。如果有，表示字元數量不匹配
        foreach ($charCount as $count) {
            if ($count !== 0) {
                return false;
            }
        }
        
        return true; // 所有計數都為零，是字母異位詞
    }
}
?>

---

二元搜尋法 (Binary Search) 🔎

二元搜尋法（Binary Search）是一種在已排序的集合中查找特定元素的演算法。它透過不斷地將搜尋範圍減半，來快速定位目標元素。其時間複雜度為 O(logn)，遠優於線性搜尋的 O(n)。

搭配例題１｜ (035) Search Insert Position

問題描述

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(logn) runtime complexity.

給定一個已排序且不含重複數字的整數陣列 nums 和一個目標值 target，如果 target 存在於陣列中，則返回它的索引。如果 target 不存在，則返回它將被按順序插入的位置索引。

你必須編寫一個時間複雜度為 O(logn) 的演算法。

Example 1:

Input: nums = [1,3,5,6], target = 5

Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2

Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7

Output: 4

解題思路

本題要求在已排序陣列中搜尋元素或其插入位置，且要求 O(logn) 的時間複雜度，這明顯是二元搜尋法的應用。

二元搜尋法的關鍵在於如何定義搜尋範圍（left 和 right 指針）以及在迴圈結束時如何處理找不到目標值的情況。

二元搜尋演算法步驟：

1. 初始化：

   • 設 left = 0，表示搜尋範圍的起點。

   • 設 right = count(nums) - 1，表示搜尋範圍的終點。

2. 迴圈：

   • 當 left <= right 時，持續執行迴圈。

   • 計算中間索引： mid = floor(($left + $right) / 2)。使用 floor 確保向下取整。

   • 比較 nums[mid] 與 target：

     • 如果 nums[mid] == target，表示找到目標值，直接返回 mid。

     • 如果 nums[mid] < target，表示目標值在中間元素 nums[mid] 的右側。因此，將 left 指針移動到 mid + 1，繼續在右半部分搜尋。

     • 如果 nums[mid] > target，表示目標值在中間元素 nums[mid] 的左側。因此，將 right 指針移動到 mid - 1，繼續在左半部分搜尋。

3. 處理找不到的情況：

   • 如果迴圈結束時（即 left > right）仍未找到目標值，這表示 target 不存在於陣列中。此時，left 指針會指向 target 應該被插入的位置。

   • 舉例說明：

     • 如果 nums = [1,3,5,6], target = 2：

       • 初始 left = 0, right = 3。

       • mid = 1, nums[1] = 3。因為 3 > 2，所以 right 移動到 mid - 1 = 0。

       • 當前 left = 0, right = 0。

       • mid = 0, nums[0] = 1。因為 1 < 2，所以 left 移動到 mid + 1 = 1。

       • 此時 left = 1, right = 0，不滿足 left <= right 條件，迴圈結束。

     • 迴圈結束後，left 的值為 1，這正是 2 應該被插入的位置。

時間複雜度： O(logn)。每次迭代都將搜尋範圍減半。

空間複雜度： O(1)。只使用了常數額外的變數。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function searchInsert($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;

        // 當 left 指針不超過 right 指針時，持續搜尋
        while ($left <= $right) {
            // 計算中間索引，使用 floor 確保向下取整
            $mid = floor(($left + $right) / 2);

            // 如果找到目標值，直接返回其索引
            if ($nums[$mid] == $target) {
                return $mid;
            } 
            // 如果中間值小於目標值，表示目標值在右半部分，移動 left 指針
            elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } 
            // 如果中間值大於目標值，表示目標值在左半部分，移動 right 指針
            else {
                $right = $mid - 1;
            }
        }
        
        // 如果迴圈結束仍未找到目標值，left 指針將指向目標值應該插入的位置
        return $left;
    }
}
?>

---

搭配例題２｜ (278) First Bad Version

問題描述

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

你是一名產品經理，目前正在帶領團隊開發新產品。不幸的是，你產品的最新版本未能通過品質檢查。由於每個版本都是基於前一個版本開發的，所以如果一個版本是錯誤的，那麼它之後的所有版本也都將是錯誤的。

假設你有 n 個版本 [1, 2, ..., n]，你想找到第一個錯誤的版本。

你可以使用一個 API 函式 bool isBadVersion(version)，它會返回 true 如果 version 是錯誤的，否則返回 false。實現一個函式來找出第一個錯誤的版本。你應該盡量減少對 API 的呼叫次數。

Example:

Input: n = 5, bad = 4 (where bad = 4 implies isBadVersion(4) returns true and all subsequent versions are bad)

isBadVersion(3) -> false

isBadVersion(5) -> true

isBadVersion(4) -> true

Output: 4

解題思路

這是一個典型的二分搜尋法應用題。由於所有錯誤版本都出現在第一個錯誤版本之後，這滿足二分搜尋法的「單調性」條件。我們可以在版本範圍 [1, n] 中進行搜尋，每次將搜尋範圍縮小一半，以最小化對 isBadVersion API 的呼叫次數。

二分搜尋演算法步驟：

1. 設定搜尋範圍：

   • 設 left = 1，表示搜尋範圍的起點（版本號從 1 開始）。

   • 設 right = n，表示搜尋範圍的終點。

   • 初始化 first_bad 為 n，用來儲存目前找到的第一個錯誤版本。我們最終會返回這個值。

2. 迴圈：

   • 當 left <= right 時，持續執行迴圈。

   • 計算中間版本： mid = floor(($left + $right) / 2)。為了避免 left + right 可能的整數溢位（雖然在 PHP 中通常不是問題，但在其他語言中可能是），更安全的寫法是 mid = $left + floor(($right - $left) / 2)。

   • 呼叫 API 判斷 isBadVersion(mid)：

     • 如果 isBadVersion(mid) 返回 true，這表示 mid 是一個錯誤版本。它可能是第一個錯誤版本，也可能不是（因為它之前的版本可能也是錯誤的）。所以，我們將 first_bad 更新為 mid（因為我們找到了一個錯誤版本），然後將搜尋範圍的右邊界 right 縮小為 mid - 1，繼續在 mid 的左側搜尋，看看是否能找到更早的錯誤版本。

     • 如果 isBadVersion(mid) 返回 false，這表示 mid 是一個「好的」版本。那麼，第一個錯誤版本一定在 mid 的右側（因為 mid 和它之前的所有版本都是好的）。因此，我們將搜尋範圍的左邊界 left 擴大為 mid + 1。

3. 返回：

   • 迴圈結束時（即 left > right），first_bad 所儲存的值就是我們找到的第一個錯誤版本。

這種方法將 API 的呼叫次數從線性的 O(n) 降到了對數級別的 O(logn)。

PHP 程式碼

PHP

<?php

// 這是 LeetCode 提供的抽象類和函式，你不需要自己實現
// class SVNRepo {
//     public function isBadVersion($version);
// }

/* The isBadVersion API is defined in the parent class.
      bool isBadVersion(int version); */

class Solution extends SVNRepo {
    /**
     * @param Integer $n
     * @return Integer
     */
    function firstBadVersion($n) {
        $left = 1;
        $right = $n;
        $first_bad = $n; // 初始化為 n，如果沒有錯誤版本，通常會返回 n 或根據題目定義

        while ($left <= $right) {
            // 計算中間版本號
            // 避免 $left + $right 溢位 (雖然 PHP 整數通常不會，但最佳實踐)
            $mid = $left + floor(($right - $left) / 2);

            // 呼叫 isBadVersion API 判斷當前版本是否錯誤
            if ($this->isBadVersion($mid)) {
                // 如果 mid 是錯誤的，它可能是第一個錯誤版本
                // 儲存 mid，並嘗試在左半部分尋找更早的錯誤版本
                $first_bad = $mid;
                $right = $mid - 1;
            } else {
                // 如果 mid 是好的，則第一個錯誤版本一定在 mid 的右邊
                $left = $mid + 1;
            }
        }

        return $first_bad; // 返回找到的第一個錯誤版本
    }
}
?>

---

鏈結串列 (Linked List) 🔗

鏈結串列（Linked List）是一種線性資料結構，不同於陣列，它不將元素儲存在連續的記憶體位置。相反，鏈結串列中的每個元素（稱為節點）都包含資料以及指向下一個節點的參考（指標）。這使得鍊結串列在插入和刪除元素時非常高效，而不需要像陣列那樣移動大量元素。

搭配例題１｜ (083) Remove Duplicates from Sorted List

問題描述

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

給定一個已排序的鍊結串列 head，刪除所有重複的元素，使得每個元素只出現一次。返回已排序的鍊結串列。

Example 1:

Input: head = [1,1,2]

Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]

Output: [1,2,3]

解題思路

本題的關鍵在於鍊結串列是已排序的。這意味著所有重複的元素都一定會相鄰出現。這一特性使得我們可以使用一個簡單的單指針迭代法來原地解決問題，而無需額外的空間。

單指針迭代演算法步驟：

1. 處理空鍊結串列： 如果輸入的 head 為 null，表示鍊結串列是空的，直接返回 null。

2. 初始化指針： 創建一個名為 current 的指針，將它指向鍊結串列的頭節點 head。這個指針將用來遍歷整個鍊結串列。

3. 迭代遍歷： 進入一個 while 迴圈，條件是 current 節點存在，並且 current 的下一個節點 current->next 也存在（這樣我們才能比較當前節點和下一個節點）。

4. 比較與刪除： 在迴圈內部：

   • 如果 current->val === current->next->val： 這表示我們找到了一對重複的元素。我們需要將 current->next 節點從鍊結串列中刪除。刪除的方法是：將 current->next 直接指向 current->next->next。這樣，current->next 原本指向的重複節點就被跳過了。重要： 在這種情況下，我們不移動 current 指針。因為新的 current->next 可能仍然是重複的（例如 1->1->1->2，處理完第一個 1->1 後，current 仍然指向第一個 1，新的 current->next 仍然是 1），我們需要繼續比較它。

   • 如果 current->val !== current->next->val： 這表示當前節點和下一個節點的值不同，沒有重複。我們可以安全地將 current 指針移動到下一個節點，即 current = current->next，繼續遍歷。

5. 返回結果： 迴圈結束後，所有重複的元素都已被移除。直接返回原始的頭節點 head。

這種方法的優點是它是在原地（in-place）操作，不需要創建新的節點，因此空間複雜度為 O(1)。時間複雜度為 O(n)，其中 n 是鍊結串列的長度，因為我們只需遍歷每個節點一次。

PHP 程式碼

PHP

<?php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 * public $val = 0;
 * public $next = null;
 * function __construct($val = 0, $next = null) {
 * $this->val = $val;
 * $this->next = $next;
 * }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function deleteDuplicates($head) {
        // 如果鍊結串列為空，直接返回
        if ($head === null) {
            return $head;
        }

        $current = $head; // 初始化一個指針指向頭節點

        // 當前節點和下一個節點都存在時，持續遍歷
        while ($current !== null && $current->next !== null) {
            // 如果當前節點的值與下一個節點的值相同，表示有重複
            if ($current->val === $current->next->val) {
                // 跳過重複的節點，將 current 的 next 指向下下個節點
                $current->next = $current->next->next;
            } else {
                // 如果沒有重複，移動到下一個節點
                $current = $current->next;
            }
        }

        // 返回處理後的頭節點
        return $head;
    }
}
?>

---

搭配例題２｜ (021) Merge Two Sorted Lists

問題描述

Merge the two sorted linked lists list1 and list2 into one single sorted linked list. The list should be made by splicing together the nodes of the first two lists.

將兩個已排序的鍊結串列 list1 和 list2 合併為一個新的已排序鍊結串列。新的鍊結串列應該是透過拼接 list1 和 list2 的節點來完成的。

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []

Output: []

Example 3:

Input: list1 = [], list2 = [0]

Output: [0]

解題思路

解決這個問題最常見的方法是使用迭代法。由於兩個輸入鍊結串列都已經排序，我們只需要遍歷它們，並將節點按順序添加到一個新的鍊結串列中。

1. 建立虛擬頭節點 (Dummy Node)：

   • 我們不直接操作新的鍊結串列的頭部，因為在合併過程中，我們需要不斷地添加節點。創建一個名為 dummyHead 的虛擬節點會讓操作更簡單。它不會包含任何值，只是一個佔位符，用來標識新鍊結串列的起點。

   • 建立一個 current 指針，並將它指向 dummyHead。這個 current 指針將會用來遍歷新鍊結串列，並在尾部添加節點。

2. 迭代合併：

   • 當 list1 和 list2 都沒有遍歷完時，進入迴圈。

   • 在迴圈中，比較 list1 和 list2 當前節點的值。

   • 如果 list1->val <= list2->val，則將 list1 的當前節點接在 current 指針之後 (current->next = list1)，然後將 list1 指針前移 (list1 = list1->next)。

   • 否則，將 list2 的當前節點接在 current 指針之後 (current->next = list2)，然後將 list2 指針前移 (list2 = list2->next)。

   • 無論哪種情況，都將 current 指針前移 (current = current->next)，準備好接下一個節點。

3. 處理剩餘節點：

   • 當上述迴圈結束時，其中一個鍊結串列可能還有剩餘的節點（因為它們的長度可能不同）。由於這些剩餘節點已經排序，我們只需將剩餘的整個鍊結串列直接接在 current 指針之後即可。

   • 如果 list1 還有剩餘，current->next = list1。

   • 如果 list2 還有剩餘，current->next = list2。

4. 返回結果：

   • 合併完成後，新的已排序鍊結串列的頭節點就是 dummyHead 的下一個節點 (dummyHead->next)。

這種方法的時間複雜度是 $O(m+n)$，其中 m 和 n 分別是兩個鍊結串列的長度，因為我們只需遍歷每個節點一次。空間複雜度是 O(1)，因為我們只使用了幾個指針，沒有額外的儲存空間。

PHP 程式碼

PHP

<?php

/**
 * Definition for a singly-linked list.
 * class ListNode {
 * public $val = 0;
 * public $next = null;
 * function __construct($val = 0, $next = null) {
 * $this->val = $val;
 * $this->next = $next;
 * }
 * }
 */
class Solution {

    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        // 創建一個虛擬頭節點，簡化合併邏輯
        $dummyHead = new ListNode();
        $current = $dummyHead; // current 指針用於構建新鍊結串列

        // 遍歷兩個鍊結串列，直到其中一個為空
        while ($list1 !== null && $list2 !== null) {
            // 比較兩個鍊結串列當前節點的值
            if ($list1->val <= $list2->val) {
                // 將較小值的節點連接到新鍊結串列的尾部
                $current->next = $list1;
                $list1 = $list1->next; // 移動 list1 指針
            } else {
                $current->next = $list2;
                $list2 = $list2->next; // 移動 list2 指針
            }
            // 移動新鍊結串列的 current 指針到剛添加的節點
            $current = $current->next;
        }

        // 將非空的鍊結串列剩餘部分直接接在新鍊結串列的尾部
        // 因為它們已經排序，所以可以直接連接
        if ($list1 !== null) {
            $current->next = $list1;
        } elseif ($list2 !== null) {
            $current->next = $list2;
        }

        // 返回虛擬頭節點的下一個節點，即新的鍊結串列的真正頭部
        return $dummyHead->next;
    }
}
?>

二元樹 (Binary Tree) 🌳

二元樹（Binary Tree）是一種每個節點最多有兩個子節點的樹狀資料結構，通常被稱為左子節點和右子節點。它廣泛應用於資料組織、搜尋演算法和表達層次結構。理解二元樹的結構和遍歷方式是許多複雜演算法的基礎。

搭配例題１｜ (100) Same Tree

問題描述

Given the roots of two binary trees p and q, return true if they are the same or false otherwise.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

給定兩個二元樹的根節點 p 和 q，判斷它們是否相同。如果相同則返回 true，否則返回 false。

兩個二元樹被認為是相同的，如果它們結構上相同，並且節點具有相同的值。

Example 1:

Input: p = [1,2,3], q = [1,2,3]

Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]

Output: false

解題思路

判斷兩棵二元樹是否相同，本質上是一個遞迴問題。我們需要同時遍歷兩棵樹，並在每一步檢查三個關鍵條件：

1. 節點存在性檢查：

   • 如果 p 和 q 都為 null，則視為相同（兩棵空樹）。

   • 如果只有 p 為 null 而 q 不為 null (或反之)，則它們不同。

2. 節點值檢查：

   • 如果 p 和 q 都存在，但它們的值 p->val 不等於 q->val，則兩棵樹不同。

3. 遞迴檢查子樹：

   • 如果當前節點的值相同，我們還需要遞迴地檢查它們的左子樹是否相同 (isSameTree(p->left, q->left))，以及右子樹是否相同 (isSameTree(p->right, q->right))。

   • 只有當這兩個遞迴檢查都返回 true 時，我們才能說當前節點及其子樹是相同的。

遞迴演算法步驟總結：

• 基本情況 (Base Cases)：

  • if ($p === null && $q === null) return true

  • if ($p === null || $q === null) return false

  • if ($p->val !== $q->val) return false

• 遞迴步驟 (Recursive Step)：

  • return $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right);

此方法的時間複雜度是 O(N)，其中 N 是較小樹的節點數（因為我們最多訪問每個節點一次）。空間複雜度是 O(H)，其中 H 是樹的高度，因為這是在遞迴呼叫堆疊上消耗的空間。在最壞情況下（斜樹，例如只有左子節點或只有右子節點），H 可以是 N，所以空間複雜度可能是 O(N)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    /**
     * @param TreeNode $p
     * @param TreeNode $q
     * @return Boolean
     */
    function isSameTree($p, $q) {
        // 基本情況 1: 兩個節點都為 null，它們是相同的
        if ($p === null && $q === null) {
            return true;
        }

        // 基本情況 2: 只有一個節點為 null，它們不同
        if ($p === null || $q === null) {
            return false;
        }

        // 基本情況 3: 兩個節點的值不同，它們不同
        if ($p->val !== $q->val) {
            return false;
        }

        // 遞迴檢查左右子樹
        // 只有當左子樹相同且右子樹也相同時，才返回 true
        return $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right);
    }
}
?>

---

搭配例題２｜ (110) Balanced Binary Tree

問題描述

Given the root of a binary tree, determine if it is a height-balanced binary tree.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

給定一個二元樹的根節點，判斷它是否是一個高度平衡的二元樹。

對於此問題，高度平衡二元樹的定義是：對於樹中的每個節點，其左右兩個子樹的深度差的絕對值不超過 1。

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]

Output: false

解題思路

判斷一棵二元樹是否平衡，需要同時考慮兩個條件：

1. 每個節點的左右子樹深度差絕對值不超過 1。

2. 每個節點的左右子樹本身也是平衡的。

這是一個適合用遞迴解決的問題。常見的方法是後序遍歷（Post-order Traversal），因為我們需要先知道子樹的高度才能判斷父節點的平衡性。

我們將設計一個輔助函式 checkHeightAndBalance(node)，它有兩個職責：

1. 計算當前節點為根的子樹的高度。

2. 在計算過程中判斷子樹是否平衡。如果發現子樹不平衡，則立即返回一個特殊值（例如 -1），表示此樹不平衡。

遞迴輔助函式 checkHeightAndBalance(node)：

• 基本情況 (Base Case)：

  • 如果 node 為 null，返回 0 (空樹的高度為 0，且視為平衡)。

• 遞迴步驟 (Recursive Step)：

  • 遞迴計算左子樹： 呼叫 checkHeightAndBalance(node->left)，得到左子樹的高度 leftHeight。

  • 提前判斷： 如果 leftHeight 返回 -1，表示左子樹已經不平衡，則整棵樹（包括當前節點）也不平衡，直接返回 -1。

  • 遞迴計算右子樹： 呼叫 checkHeightAndBalance(node->right)，得到右子樹的高度 rightHeight。

  • 提前判斷： 如果 rightHeight 返回 -1，表示右子樹已經不平衡，則整棵樹也不平衡，直接返回 -1。

  • 檢查當前節點的平衡性：

    • 計算左右子樹的高度差絕對值：abs(leftHeight - rightHeight)。

    • 如果此差值大於 1，則當前節點的子樹不平衡，返回 -1。

  • 返回當前節點的高度：

    • 如果當前節點的子樹是平衡的，則返回當前節點的高度：max(leftHeight, rightHeight) + 1。

主函式 isBalanced(root) 只需要呼叫 checkHeightAndBalance(root)，並檢查其返回值是否為 -1。如果不是 -1，則表示樹是平衡的。

此方法的時間複雜度是 O(N)，其中 N 是樹的節點數，因為每個節點只會被訪問一次。空間複雜度是 O(H)，其中 H 是樹的高度，用於遞迴呼叫堆疊。在最壞情況下（斜樹），H 可以是 N，所以空間複雜度可能是 O(N)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isBalanced($root) {
        // 如果輔助函式返回 -1，表示樹不平衡
        return $this->checkHeightAndBalance($root) !== -1;
    }

    /**
     * 輔助函式：計算節點高度並檢查平衡性
     * 如果子樹不平衡，返回 -1
     * 否則，返回子樹的高度
     * @param TreeNode $node
     * @return Integer
     */
    private function checkHeightAndBalance($node) {
        // 基本情況: 空節點的高度為 0，且視為平衡
        if ($node === null) {
            return 0;
        }

        // 遞迴計算左子樹的高度和平衡性
        $leftHeight = $this->checkHeightAndBalance($node->left);
        // 如果左子樹不平衡 (返回 -1)，則整棵樹不平衡
        if ($leftHeight === -1) {
            return -1;
        }

        // 遞迴計算右子樹的高度和平衡性
        $rightHeight = $this->checkHeightAndBalance($node->right);
        // 如果右子樹不平衡 (返回 -1)，則整棵樹不平衡
        if ($rightHeight === -1) {
            return -1;
        }

        // 檢查當前節點的左右子樹高度差是否超過 1
        if (abs($leftHeight - $rightHeight) > 1) {
            return -1; // 不平衡
        }

        // 如果平衡，返回當前節點的高度
        // 當前節點的高度 = max(左子樹高度, 右子樹高度) + 1
        return max($leftHeight, $rightHeight) + 1;
    }
}
?>

---

遞迴與迭代解 (Recursive/Iterative Solution) 🔄

遞迴（Recursion）和迭代（Iteration）是兩種常見的程式設計範式，它們在解決重複性問題時都非常有用。遞迴通常透過函數呼叫自身來解決問題，而迭代則使用迴圈結構。許多演算法問題，特別是樹和圖的問題，都可以用這兩種方式來解決。理解它們的轉換和各自的優缺點對於寫出高效且清晰的程式碼至關重要。

搭配例題１｜ (101) Symmetric Tree

問題描述

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

給定一個二元樹的根節點 root，檢查它是否是其自身的鏡像（即，圍繞其中心對稱）。

Example 1:

Input: root = [1,2,2,3,4,4,3]

Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]

Output: false

解題思路

判斷一棵二元樹是否對稱，可以看作是判斷它的左子樹和右子樹是否互為鏡像。這同樣是一個適合用遞迴或迭代解決的問題。

遞迴解：

我們需要一個輔助函式 isMirror(node1, node2) 來判斷兩棵子樹 node1 和 node2 是否互為鏡像。

1. 基本情況 (Base Cases)：

   • 如果 node1 和 node2 都為 null，返回 true (兩棵空樹互為鏡像)。

   • 如果只有 node1 為 null 而 node2 不為 null (或反之)，返回 false (一棵空樹和一棵非空樹不互為鏡像)。

   • 如果 node1 和 node2 都存在，但它們的值 node1->val 不等於 node2->val，返回 false (值不同)。

2. 遞迴步驟 (Recursive Step)：

   • 如果上述基本情況都沒有觸發（即 node1 和 node2 都存在且值相同），則遞迴地呼叫 isMirror 函式來檢查：

     • node1 的左子樹是否與 node2 的右子樹互為鏡像 (isMirror(node1->left, node2->right))。

     • node1 的右子樹是否與 node2 的左子樹互為鏡像 (isMirror(node1->right, node2->left))。

   • 只有當這兩個遞迴呼叫都返回 true 時，才返回 true。

主函式 isSymmetric(root) 只需要呼叫 isMirror(root->left, root->right)。如果 root 為 null，直接返回 true。

時間複雜度： O(N)，其中 N 是樹的節點數，因為每個節點最多訪問一次。

空間複雜度： O(H)，其中 H 是樹的高度，用於遞迴呼叫堆疊。最壞情況下（斜樹），H 可以是 N，所以空間複雜度可能是 O(N)。

迭代解 (使用佇列 - Queue / BFS)：

迭代方法通常使用佇列（廣度優先搜尋 BFS 層次遍歷）來實現。我們將需要比較的節點對放入佇列中。

1. 初始化：

   • 如果 root 為 null，返回 true。

   • 創建一個佇列 queue。

   • 將 root->left 和 root->right 這兩個節點放入佇列中，作為初始的比較對。

2. 遍歷：

   • 當佇列不為空時，持續執行迴圈。

   • 從佇列中取出兩個節點，分別命名為 t1 和 t2。

   • 檢查基本情況：

     • 如果 t1 和 t2 都為 null，則這對節點是對稱的，繼續下一輪迴圈。

     • 如果只有一個為 null (或 t1->val !== t2->val)，則不對稱，立即返回 false。

   • 將下一對節點放入佇列：

     • 將 t1 的左子樹 (t1->left) 和 t2 的右子樹 (t2->right) 放入佇列。

     • 將 t1 的右子樹 (t1->right) 和 t2 的左子樹 (t2->left) 放入佇列。

3. 返回：

   • 如果迴圈正常結束（即所有節點對都檢查完畢，且沒有返回 false），則表示所有節點都對稱，返回 true。

時間複雜度： O(N)，因為每個節點會被放入和取出佇列一次。

空間複雜度： O(W)，其中 W 是樹的最大寬度。在最壞情況下（滿二元樹的最後一層），W 可以是 N/2，所以空間複雜度是 O(N)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    /**
     * 遞迴解法
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetricRecursive($root) {
        if ($root === null) {
            return true; // 空樹是對稱的
        }
        // 呼叫輔助函式判斷左右子樹是否互為鏡像
        return $this->isMirror($root->left, $root->right);
    }

    /**
     * 輔助函式：判斷兩棵樹是否互為鏡像
     * @param TreeNode $t1
     * @param TreeNode $t2
     * @return Boolean
     */
    private function isMirror($t1, $t2) {
        // 兩個節點都為 null，互為鏡像
        if ($t1 === null && $t2 === null) {
            return true;
        }
        // 只有一個節點為 null，或值不相等，則不互為鏡像
        if ($t1 === null || $t2 === null || $t1->val !== $t2->val) {
            return false;
        }
        // 遞迴檢查 t1 的左子樹與 t2 的右子樹是否鏡像，以及 t1 的右子樹與 t2 的左子樹是否鏡像
        return $this->isMirror($t1->left, $t2->right) && $this->isMirror($t1->right, $t2->left);
    }


    /**
     * 迭代解法 (使用佇列 / BFS)
     * @param TreeNode $root
     * @return Boolean
     */
    function isSymmetric($root) {
        if ($root === null) {
            return true; // 空樹是對稱的
        }

        // 創建一個佇列並將根節點的左右子樹放入
        $queue = [];
        array_push($queue, $root->left);
        array_push($queue, $root->right);

        // 當佇列不為空時持續遍歷
        while (!empty($queue)) {
            // 從佇列中取出兩個節點進行比較
            $t1 = array_shift($queue);
            $t2 = array_shift($queue);

            // 如果兩個都為 null，表示這對節點對稱，繼續下一輪
            if ($t1 === null && $t2 === null) {
                continue;
            }

            // 如果只有一個為 null 或值不相等，表示不對稱
            if ($t1 === null || $t2 === null || $t1->val !== $t2->val) {
                return false;
            }

            // 將下一對需要比較鏡像關係的子節點放入佇列
            // t1 的左子樹應與 t2 的右子樹對稱
            array_push($queue, $t1->left);
            array_push($queue, $t2->right);

            // t1 的右子樹應與 t2 的左子樹對稱
            array_push($queue, $t1->right);
            array_push($queue, $t2->left);
        }

        // 如果所有檢查都通過，則樹是對稱的
        return true;
    }
}
?>

---

搭配例題２｜ (617) Merge Two Binary Trees

問題描述

You are given two binary trees root1 and root2.

Imagine that when you overlap the two trees, some nodes of the two trees overlap while the others don't. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then their values should be summed up as the new node's value. Otherwise, the non-null node will be used as the node of the new tree.

Return the merged tree.

Note that the merging process must start from the roots of both trees.

給定兩棵二元樹 root1 和 root2。

想像將這兩棵樹重疊時，有些節點會重疊而另一些則不會。你需要將這兩棵樹合併為一棵新的二元樹。合併規則是：如果兩個節點重疊，它們的值應相加作為新節點的值。否則，非 null 的節點將作為新樹的節點。

返回合併後的樹。

注意，合併過程必須從兩棵樹的根節點開始。

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]

Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]

Output: [2,2]

解題思路

合併兩棵二元樹是一個典型的遞迴問題。我們可以同時遍歷兩棵樹，並在每個對應位置進行操作。也可以使用迭代方法（廣度優先搜尋 BFS）。

遞迴解：

1. 基本情況 (Base Cases)：

   • 如果 root1 為 null，直接返回 root2 (因為 root2 中可能還有節點，這些節點需要被包含在合併後的樹中)。

   • 如果 root2 為 null，直接返回 root1 (同理)。

2. 遞迴步驟 (Recursive Step)：

   • 如果 root1 和 root2 都不是 null：

     • 我們將修改其中一棵樹（例如 root1）來作為合併後的結果。將 root1 的值更新為 root1->val + root2->val。

     • 遞迴地合併左子樹： root1->left = mergeTrees(root1->left, root2->left)。

     • 遞迴地合併右子樹： root1->right = mergeTrees(root1->right, root2->right)。

     • 返回修改後的 root1。

這種方法通常會修改其中一個輸入樹 (root1 或 root2) 來作為合併後的結果，這樣可以節省空間。

時間複雜度： O(M)，其中 M 是兩棵樹中較大樹的節點總數（即所有重疊和非重疊節點的總數）。因為我們只訪問每個節點一次。

空間複雜度： O(H)，其中 H 是合併後樹的高度，用於遞迴呼叫堆疊。最壞情況下（斜樹），H 可以是 M，所以空間複雜度可能是 O(M)。

迭代解 (使用佇列 / BFS)：

迭代方法通常使用佇列（廣度優先搜尋 BFS）來實現。

1. 初始化：

   • 如果 root1 為 null，返回 root2。

   • 如果 root2 為 null，返回 root1。

   • 創建一個佇列 queue。

   • 將根節點對 [root1, root2] 放入佇列中作為起始。

2. 遍歷：

   • 當佇列不為空時，持續執行迴圈。

   • 從佇列中取出當前的兩個節點，分別命名為 n1 和 n2。

   • 合併值： 將 n2 的值加到 n1 上：n1->val += n2->val。

   • 處理左子節點：

     • 如果 n1->left 和 n2->left 都存在，將這對子節點 [n1->left, n2->left] 放入佇列，以便在下一個迭代中合併它們。

     • 如果 n1->left 不存在但 n2->left 存在，將 n2->left 直接連接到 n1->left (n1->left = n2->left)。

   • 處理右子節點：

     • 如果 n1->right 和 n2->right 都存在，將這對子節點 [n1->right, n2->right] 放入佇列。

     • 如果 n1->right 不存在但 n2->right 存在，將 n2->right 直接連接到 n1->right (n1->right = n2->right)。

3. 返回：

   • 迴圈結束後，返回 root1（因為我們是在 root1 上進行修改）。

時間複雜度： O(M)，其中 M 是兩棵樹中較大樹的節點總數。

空間複雜度： O(W)，其中 W 是樹的最大寬度。最壞情況下為 O(M)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    /**
     * 遞迴解法
     * @param TreeNode $root1
     * @param TreeNode $root2
     * @return TreeNode
     */
    function mergeTrees($root1, $root2) {
        // 基本情況: 如果 root1 為空，則返回 root2
        if ($root1 === null) {
            return $root2;
        }
        // 基本情況: 如果 root2 為空，則返回 root1
        if ($root2 === null) {
            return $root1;
        }

        // 如果兩個節點都存在，則將它們的值相加
        // 這裡直接修改 root1 的值，將 root1 作為合併後的結果樹
        $root1->val += $root2->val;

        // 遞迴地合併左子樹
        $root1->left = $this->mergeTrees($root1->left, $root2->left);
        // 遞迴地合併右子樹
        $root1->right = $this->mergeTrees($root1->right, $root2->right);

        // 返回修改後的 root1
        return $root1;
    }


    /**
     * 迭代解法 (使用佇列 / BFS)
     * @param TreeNode $root1
     * @param TreeNode $root2
     * @return TreeNode
     */
    function mergeTreesIterative($root1, $root2) {
        // 處理特殊情況：如果任何一個根節點為空，直接返回另一個（或 null）
        if ($root1 === null) {
            return $root2;
        }
        if ($root2 === null) {
            return $root1;
        }

        // 創建一個佇列，儲存節點對 [node1, node2]
        $queue = [];
        array_push($queue, [$root1, $root2]);

        // 遍歷佇列
        while (!empty($queue)) {
            // 取出節點對
            list($n1, $n2) = array_shift($queue);

            // 確保兩個節點都非 null 且需要合併，否則跳過
            // 實際上，由於我們的 push 邏輯，這裡的 n1, n2 不會同時為 null
            // 但為嚴謹性可以保留此檢查
            if ($n1 === null || $n2 === null) {
                continue;
            }

            // 合併節點值：將 n2 的值加到 n1 上
            $n1->val += $n2->val;

            // 處理左子樹
            if ($n1->left !== null && $n2->left !== null) {
                // 如果兩者左子樹都存在，將它們放入佇列等待合併
                array_push($queue, [$n1->left, $n2->left]);
            } elseif ($n1->left === null && $n2->left !== null) {
                // 如果只有 n2 的左子樹存在，直接將 n2 的左子樹連接到 n1 的左側
                // 這樣 n2 的這部分子樹及其後代會被包含到結果樹中
                $n1->left = $n2->left;
            }
            // 如果只有 n1 的左子樹存在，則不需要操作，保持現狀，因為它已經在結果樹中

            // 處理右子樹 (邏輯同左子樹)
            if ($n1->right !== null && $n2->right !== null) {
                array_push($queue, [$n1->right, $n2->right]);
            } elseif ($n1->right === null && $n2->right !== null) {
                $n1->right = $n2->right;
            }
        }

        return $root1; // 返回修改後的 root1
    }
}
?>

---

動態規劃 (Dynamic Programming) 🧠

動態規劃（Dynamic Programming, DP）是一種透過將複雜問題分解為更小的重疊子問題，並儲存這些子問題的解，從而避免重複計算，最終得出原問題解的演算法技術。它通常用於優化具有重疊子問題和最優子結構特性的問題。DP 的核心在於定義「狀態」和「狀態轉移方程」。¹

搭配例題１｜ (062) Unique Paths²

問題描述³

There is a robot on an m x n grid. The robot is initially located at the top-left corner (grid[0][0]). The robot tries to move to th⁴e bottom-right corner (grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

一個機器人位於一個 m x n 的網格的左上角 (grid[0][0])。機器人試圖到達網格的右下角 (grid[m - 1][n - 1])。機器人在任何時候只能向下或向右移動。

給定兩個整數 m 和 n，返回機器人可以到達右下角的不同路徑的數量。

Example 1:

Input: m = 3, n = 7

Output: 28

Example 2:

Input: m = 3, n = 2

Output: 3

Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down

2. Down -> Down -> Right

3. Down -> Right -> Down

解題思路

這是一個典型的動態規劃 (Dynamic Programming) 問題。我們可以定義狀態 dp[i][j] 為從網格左上角 (0,0) 到達 (i,j) 的唯一路徑數量。

狀態轉移方程：

由於機器人只能向下或向右移動，到達 (i,j) 的路徑只能來自於 (i-1, j)（從上方移動下來）或 (i, j-1)（從左方移動過來）。因此，到達 (i,j) 的總路徑數就是到達這兩個位置的路徑數之和。

dp[i][j] = dp[i-1][j] + dp[i][j-1]

基本情況 (Base Cases)：

• 第一行： 對於第一行（i = 0），任何位置 (0, j) 都只有一條路徑到達（一直向右）。所以 dp[0][j] = 1。

• 第一列： 對於第一列（j = 0），任何位置 (i, 0) 都只有一條路徑到達（一直向下）。所以 dp[i][0] = 1。

實現細節：

1. 創建 dp 陣列： 建立一個 m x n 的二維陣列來儲存 dp 值，並將所有元素初始化為 0。

2. 填充基本情況： 將 dp 陣列的第一行和第一列的所有元素設為 1。

3. 填充其他單元格： 從 (1,1) 開始，依序遍歷所有單元格，並根據狀態轉移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1] 填充 dp[i][j]，直到 (m-1, n-1)。

時間複雜度： O(mtimesn)，因為我們需要遍歷整個 m x n 的網格一次。

空間複雜度： O(mtimesn)，用於儲存 dp 陣列。

空間優化（進階）：

注意到計算 dp[i][j] 只依賴於其上方和左方的單元格。我們可以將空間複雜度優化到 O(n) (如果用一維陣列表示列) 或 O(m) (如果用一維陣列表示行)。

優化後的思路是：只用一個一維陣列 dp[j] 表示當前行的路徑數。

初始化 dp 陣列為 n 個 1，表示第一行的所有路徑數。

然後從第二行開始（i 從 1 到 m-1），迭代每一列（j 從 1 到 n-1），更新 dp[j]：

dp[j] = dp[j] (來自上一行的 dp[j]) + dp[j-1] (來自當前行的前一個 dp[j-1])。

（注意：dp[j] 在更新前實際上代表 dp[i-1][j]，而 dp[j-1] 代表 dp[i][j-1]）。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer $m
     * @param Integer $n
     * @return Integer
     */
    function uniquePaths($m, $n) {
        // 創建一個 m x n 的二維陣列來儲存 dp 值
        // dp[i][j] 表示從 (0,0) 到 (i,j) 的唯一路徑數量
        $dp = array_fill(0, $m, array_fill(0, $n, 0));

        // 初始化第一行
        // 任何從 (0,0) 到 (0,j) 的路徑只有一條 (一直向右)
        for ($j = 0; $j < $n; $j++) {
            $dp[0][$j] = 1;
        }
        // 初始化第一列
        // 任何從 (0,0) 到 (i,0) 的路徑只有一條 (一直向下)
        for ($i = 0; $i < $m; $i++) {
            $dp[$i][0] = 1;
        }

        // 填充其餘的單元格
        // dp[i][j] = dp[i-1][j] (來自上方) + dp[i][j-1] (來自左方)
        for ($i = 1; $i < $m; $i++) {
            for ($j = 1; $j < $n; $j++) {
                $dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1];
            }
        }

        // 返回到達右下角的路徑數量
        return $dp[$m-1][$n-1];
    }
}
?>

---

搭配例題２｜ (063) Unique Paths II

問題描述

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (grid[0][0]). The robot tries to move to the bottom-right corner (grid[m-1][n-1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in the grid.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the number of unique paths will not exceed 2 * 10^9.

你被給定一個 m x n 的整數陣列 obstacleGrid。一個機器人最初位於左上角 (grid[0][0])。機器人試圖到達網格的右下角 (grid[m-1][n-1])。機器人可以在任何時候只能向下或向右移動。

在網格中，障礙物和空格分別用 1 或 0 標記。

返回機器人可以到達右下角的不同路徑的數量。

測試案例的產生確保唯一路徑的數量不會超過 2times109。

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

Output: 2

Explanation: There is one obstacle in the middle of the 3x3 grid above.

There are two ways to reach the bottom-right corner:

1. Right -> Right -> Down -> Down

2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]

Output: 1

解題思路

這是在「Unique Paths」基礎上增加了障礙物的變種問題。動態規劃的方法依然適用，但需要對狀態轉移和基本情況進行調整。

我們依然定義狀態 dp[i][j] 為從網格左上角 (0,0) 到達 (i,j) 的唯一路徑數量。

狀態轉移方程：

• 如果 obstacleGrid[i][j] 是障礙物（即 1）： 那麼機器人無法到達 (i,j)，因此到達 (i,j) 的路徑數為 0。

  dp[i][j] = 0

• 如果 obstacleGrid[i][j] 是空格（即 0）： 那麼到達 (i,j) 的路徑數是來自其上方和左方的路徑數之和。

  dp[i][j] = dp[i-1][j] + dp[i][j-1] (與 Unique Paths 相同)

基本情況 (Base Cases) 的特殊處理：

1. 起點 (0,0)：

   • 如果 obstacleGrid[0][0] 是障礙物，那麼機器人根本無法開始移動，直接返回 0。

   • 否則，dp[0][0] = 1。

2. 第一行 (0, j)：

   • 對於 dp[0][j]，如果 obstacleGrid[0][j] 是障礙物，則 dp[0][j] 為 0，並且其後續在第一行的所有單元格都將無法從 (0,0) 抵達，路徑數也應為 0。

   • 否則（obstacleGrid[0][j] 是空格），dp[0][j] 的路徑數與其左邊的節點相同：dp[0][j] = dp[0][j-1]。但這裡要特別注意，如果 dp[0][j-1] 已經是 0（因為遇到了前面的障礙物），那麼 dp[0][j] 也會是 0。

3. 第一列 (i, 0)：

   • 同理，對於 dp[i][0]，如果 obstacleGrid[i][0] 是障礙物，則 dp[i][0] 為 0，並且其後續在第一列的所有單元格都將無法從 (0,0) 抵達，路徑數也應為 0。

   • 否則（obstacleGrid[i][0] 是空格），dp[i][0] 的路徑數與其上方的節點相同：dp[i][0] = dp[i-1][0]。

實現細節：

1. 檢查起點/終點是否為障礙物： 在開始前，如果 obstacleGrid[0][0] 或 obstacleGrid[m-1][n-1] 是 1，可以直接返回 0。

2. 創建 dp 陣列： 創建一個與 obstacleGrid 相同大小的二維陣列，並初始化為 0。

3. 處理起點： 設置 dp[0][0] = 1。

4. 填充第一行和第一列： 根據上述基本情況規則（遇到障礙物後，後續路徑數均為 0）進行填充。

5. 填充其餘單元格： 從 (1,1) 開始遍歷。如果當前格 obstacleGrid[i][j] 是障礙物，dp[i][j] 設為 0。否則，使用狀態轉移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

時間複雜度： O(mtimesn)。

空間複雜度： O(mtimesn)。同樣可以優化到 O(n) 或 O(m)。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($obstacleGrid) {
        $m = count($obstacleGrid);
        $n = count($obstacleGrid[0]);

        // 如果起點或終點是障礙物，則無法到達
        if ($obstacleGrid[0][0] === 1 || $obstacleGrid[$m-1][$n-1] === 1) {
            return 0;
        }

        // 創建 dp 陣列，儲存到達每個單元格的唯一路徑數量
        $dp = array_fill(0, $m, array_fill(0, $n, 0));

        // 初始化起點：如果起點不是障礙物，則到達起點的路徑數為 1
        $dp[0][0] = 1;

        // 初始化第一行
        for ($j = 1; $j < $n; $j++) {
            // 如果當前格不是障礙物，並且它左邊的格可以到達 (dp值為1)，則它也可以到達
            // 這裡確保一旦遇到障礙物，後續的路徑數都為 0
            if ($obstacleGrid[0][$j] === 0 && $dp[0][$j-1] === 1) {
                $dp[0][$j] = 1;
            }
        }

        // 初始化第一列
        for ($i = 1; $i < $m; $i++) {
            // 如果當前格不是障礙物，並且它上方的格可以到達 (dp值為1)，則它也可以到達
            if ($obstacleGrid[$i][0] === 0 && $dp[$i-1][0] === 1) {
                $dp[$i][0] = 1;
            }
        }

        // 填充其餘的單元格
        for ($i = 1; $i < $m; $i++) {
            for ($j = 1; $j < $n; $j++) {
                // 如果當前格是障礙物，路徑數為 0
                if ($obstacleGrid[$i][$j] === 1) {
                    $dp[$i][$j] = 0;
                } else {
                    // 否則，路徑數是來自上方 ($dp[i-1][j]) 和左方 ($dp[i][j-1]) 的路徑數之和
                    $dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1];
                }
            }
        }

        return $dp[$m-1][$n-1];
    }
}
?>

---

搭配例題３｜ (198) House Robber

問題描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

你是一名專業的小偷，計畫沿著一條街搶劫房屋。每間房屋都藏有一定數量的錢，唯一阻止你搶劫它們的限制是：相鄰的房屋都連接了安全系統，如果在同一晚闖入兩間相鄰的房屋，它將自動聯繫警方。

給定一個整數陣列 nums，表示每間房屋的金額，返回你今晚可以在不驚動警方的條件下搶劫到的最高金額。

Example 1:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).

Total amount = 2 + 9 + 1 = 12.

解題思路

這是一個經典的動態規劃問題。對於每一間房屋，小偷有兩種選擇：搶劫它，或者不搶劫它。這兩種選擇會影響到下一間房屋的決策。

我們定義狀態 dp[i] 為考慮搶劫到第 i 間房屋時，能獲得的最高金額。

狀態轉移方程：

對於第 i 間房屋（索引為 i）：

1. 選擇搶劫第 i 間房屋： 如果選擇搶劫第 i 間房屋，那麼就不能搶劫其相鄰的第 i-1 間房屋。因此，當前的總金額是 nums[i] 加上搶劫到第 i-2 間房屋時所能獲得的最大金額 dp[i-2]。

   即：nums[i] + dp[i-2]

2. 選擇不搶劫第 i 間房屋： 如果選擇不搶劫第 i 間房屋，那麼當前的總金額就是搶劫到第 i-1 間房屋時所能獲得的最大金額 dp[i-1]。

   即：dp[i-1]

因此，dp[i] 應該是這兩種情況下的最大值：

dp[i] = max(nums[i] + dp[i-2], dp[i-1])

基本情況 (Base Cases)：

• 如果房屋數量為 0 (n === 0)，返回 0。

• 如果房屋數量為 1 (n === 1)，返回 nums[0]。

• dp[0] = nums[0] (搶劫第一間房屋時的最大金額)。

• dp[1] = max(nums[0], nums[1]) (搶劫前兩間房屋時的最大金額，因為不能同時搶劫，所以取兩者中較大的一個)。

實現細節：

1. 邊界情況處理： 處理 nums 為空或只有一個元素的情況。

2. 創建 dp 陣列： 創建一個大小為 n 的陣列來儲存 dp 值。

3. 填充基本情況： 設置 dp[0] 和 dp[1]。

4. 迴圈填充： 從 i = 2 開始，使用狀態轉移方程填充 dp 陣列，直到 n-1。

5. 返回結果： 返回 dp[n-1]，即搶劫所有房屋後能獲得的最大金額。

時間複雜度： O(N)，其中 N 是房屋的數量，因為我們需要遍歷陣列一次來填充 dp 陣列。

空間複雜度： O(N)，用於儲存 dp 陣列。

空間優化（進階）：O(1) 空間複雜度

注意到計算 dp[i] 只依賴於 dp[i-1] 和 dp[i-2]。這意味著我們不需要儲存整個 dp 陣列，只需要儲存前兩個狀態的最大值即可。

• 使用兩個變數：

  • prevMax (對應 dp[i-2])：儲存前前一個房屋搶劫的最大金額。

  • currMax (對應 dp[i-1])：儲存前一個房屋搶劫的最大金額。

• 在每次迭代中，計算新的最大值 newMax：newMax = max(prevMax + nums[i], currMax)。

• 然後更新 prevMax 為舊的 currMax，currMax 為 newMax。

• 最終返回 currMax。

prevMax = 0
currMax = 0
for num in nums:
    temp = currMax
    currMax = max(prevMax + num, currMax)
    prevMax = temp
return currMax

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $n = count($nums);

        // 邊界情況處理
        if ($n === 0) {
            return 0; // 沒有房屋可搶，返回 0
        }
        if ($n === 1) {
            return $nums[0]; // 只有一間房屋，直接搶它
        }

        // 創建 dp 陣列
        // dp[i] 表示搶劫到第 i 間房屋時，可以獲得的最高金額
        $dp = array_fill(0, $n, 0);

        // 初始化基本情況
        $dp[0] = $nums[0]; // 搶劫第一間房屋
        $dp[1] = max($nums[0], $nums[1]); // 搶劫前兩間房屋，取最大值（不能同時搶）

        // 從第三間房屋開始填充 dp 陣列
        for ($i = 2; $i < $n; $i++) {
            // 狀態轉移方程：
            // 選擇搶劫第 i 間：nums[i] + dp[i-2]
            // 選擇不搶劫第 i 間：dp[i-1]
            // 取兩者中的最大值
            $dp[$i] = max($nums[$i] + $dp[$i-2], $dp[$i-1]);
        }

        // 返回搶劫最後一間房屋時的最高金額
        return $dp[$n-1];
    }

    // 空間優化後的解法 (O(1) 空間)
    function robOptimized($nums) {
        $n = count($nums);

        if ($n === 0) return 0;
        if ($n === 1) return $nums[0];

        // prevMax 相當於 dp[i-2]
        // currMax 相當於 dp[i-1]
        $prevMax = 0;
        $currMax = 0;

        foreach ($nums as $num) {
            $temp = $currMax; // 暫存 currMax，它將成為下一個 prevMax
            // 計算新的 currMax: max(搶當前房屋 + prevMax, 不搶當前房屋 (currMax))
            $currMax = max($prevMax + $num, $currMax);
            $prevMax = $temp; // 更新 prevMax
        }

        return $currMax;
    }
}
?>

---

搭配例題４｜ (213) House Robber II

問題描述

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

你是一名專業的小偷，計畫沿著一條街搶劫房屋。每間房屋都藏有一定數量的錢。所有的房屋都排列成一個圓圈。這意味著第一間房屋是最後一間房屋的鄰居。同時，相鄰的房屋都連接了安全系統，如果在同一晚闖入兩間相鄰的房屋，它將自動聯繫警方。

給定一個整數陣列 nums，表示每間房屋的金額，返回你今晚可以在不驚動警方的條件下搶劫到的最高金額。

Example 1:

Input: nums = [2,3,2]

Output: 3

Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent. We should rob house 2 (money = 3).

Example 2:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount = 1 + 3 = 4.

解題思路

這是在「House Robber」基礎上增加了「房屋圍成一圈」的限制。這個限制導致了第一間房屋和最後一間房屋不能同時被搶劫，因為它們現在是相鄰的。

這個問題不能直接套用 House Robber 的 DP 狀態轉移，因為圓形的結構打破了簡單的線性 DP。但是，我們可以巧妙地將這個圓形問題分解為兩個線性的 House Robber 問題：

1. 情況一：不搶劫最後一間房屋。

   • 這時，問題就變成了搶劫從第一間房屋到倒數第二間房屋（nums[0] 到 nums[n-2]）組成的線性街區。

   • 我們可以對 nums[0 ... n-2] 這個子陣列應用 House Robber (198) 的解法。

2. 情況二：不搶劫第一間房屋。

   • 這時，問題就變成了搶劫從第二間房屋到最後一間房屋（nums[1] 到 nums[n-1]）組成的線性街區。

   • 我們可以對 nums[1 ... n-1] 這個子陣列應用 House Robber (198) 的解法。

由於這兩種情況涵蓋了所有可能的搶劫方案（因為第一間和最後一間至少有一間不會被搶），所以最終的答案就是這兩種情況下的最大值。

特殊邊界情況：

• 如果房屋數量只有一間 (n = 1)，則直接返回 nums[0]。因為此時 n-2 和 1 都會導致子陣列為空，而實際情況是它能搶劫這唯一一間房屋。

• 如果房屋數量為零 (n = 0)，則返回 0。

解決步驟：

1. 處理邊界情況： 如果 n <= 1，直接返回對應的值。

2. 定義輔助函式： 實作一個輔助函式（就是 House Robber (198) 的解法，並且最好是使用 O(1) 空間複雜度優化後的版本），用於計算給定一個線性陣列所能搶劫到的最大金額。

3. 計算兩種情況：

   • 呼叫輔助函式，計算 robRange(array_slice($nums, 0, $n - 1))。

   • 呼叫輔助函式，計算 robRange(array_slice($nums, 1))。

4. 返回最大值： 比較這兩種情況的結果，返回較大的一個。

時間複雜度： O(N)。因為我們進行了兩次 O(N) 的 House Robber 運算（兩次陣列切片和兩次遍歷）。

空間複雜度： O(N) 或 O(1)。如果 array_slice 導致新的陣列被創建，則為 O(N)。如果輔助函式使用 O(1) 的空間優化版本，那麼整體空間可以認為是 O(1) (忽略 array_slice 的臨時空間)。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums) {
        $n = count($nums);

        // 邊界情況處理
        if ($n === 0) {
            return 0;
        }
        if ($n === 1) {
            return $nums[0];
        }

        // 問題分解為兩個子問題：
        // 1. 不搶劫最後一間房屋：考慮從 nums[0] 到 nums[n-2]
        $result1 = $this->robRange(array_slice($nums, 0, $n - 1)); // 包含 0, 不包含 n-1

        // 2. 不搶劫第一間房屋：考慮從 nums[1] 到 nums[n-1]
        $result2 = $this->robRange(array_slice($nums, 1)); // 包含 1, 包含 n-1

        // 返回兩個子問題中的最大值
        return max($result1, $result2);
    }

    /**
     * 輔助函式：用於解決線性的 House Robber 問題
     * 實現與 LeetCode 198 House Robber 的 O(1) 空間優化版本相同
     * @param Integer[] $nums
     * @return Integer
     */
    private function robRange($nums) {
        $n = count($nums);

        if ($n === 0) return 0;
        if ($n === 1) return $nums[0];

        $prevMax = 0; // 對應 dp[i-2]
        $currMax = 0; // 對應 dp[i-1]

        foreach ($nums as $num) {
            $temp = $currMax; // 暫存 currMax，它將成為下一個 prevMax
            $currMax = max($prevMax + $num, $currMax); // 計算新的 currMax
            $prevMax = $temp; // 更新 prevMax
        }

        return $currMax;
    }
}
?>

好的，這是一份為您精心準備的 LeetCode 刷題學習筆記，專為 PHP 工程師設計，內容涵蓋您指定的所有主題與例題。這份筆記旨在提供清晰的問題解析、多角度的解題思路以及可直接運行的 PHP 程式碼，助您在演算法領域更上一層樓！

---

二元樹走訪 (Traversal) 🚶

二元樹走訪（Binary Tree Traversal）是指按照特定順序訪問樹中所有節點的過程。主要有三種標準走訪方式：前序（Pre-order）、中序（In-order）和後序（Post-order），它們都可以用遞迴或迭代（使用堆疊）實現。此外，**層次走訪（Level Order Traversal）**則使用佇列（Queue）實現。

搭配例題１｜ (094) Binary Tree Inorder Traversal

問題描述

Given the root of a binary tree, return the inorder traversal of its nodes' values.

給定一個二元樹的根節點 root，返回其中序遍歷的節點值列表。

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Example 2:

Input: root = []

Output: []

Example 3:

Input: root = [1]

Output: [1]

解題思路

中序遍歷的順序是：左子樹 -> 根節點 -> 右子樹。這意味著我們會先遍歷完左子樹的所有節點，然後訪問根節點，最後再遍歷右子樹。

遞迴解法：

遞迴是實現樹遍歷最直觀的方式。

1. 基本情況： 如果當前節點為 null，則直接返回。

2. 遞迴步驟：

   • 遞迴地對左子樹進行中序遍歷：inorderTraversal(node->left)。

   • 訪問當前根節點：將 node->val 加入結果列表。

   • 遞迴地對右子樹進行中序遍歷：inorderTraversal(node->right)。

需要一個外部陣列來儲存遍歷結果。

時間複雜度： O(N)，其中 N 是樹的節點數，因為每個節點都會被訪問一次。

空間複雜度： O(H)，其中 H 是樹的高度，用於遞迴呼叫堆疊。在最壞情況下（斜樹），H 可以是 N，所以空間複雜度可能是 O(N)。

迭代解法 (使用堆疊 - Stack)：

迭代解法通常使用一個堆疊來模擬遞迴的行為。

1. 初始化：

   • 創建一個空的結果陣列 result。

   • 創建一個空的堆疊 stack。

   • 創建一個 current 指針，初始化為 root。

2. 遍歷：

   • 當 current 指針不為 null 或堆疊不為空時，持續執行迴圈。

   • 深入左子樹： 當 current 不為 null 時，將 current 推入堆疊，並將 current 移動到其左子節點 (current = current->left)。重複此步驟直到 current 為 null（即到達最左邊的節點）。

   • 訪問節點： 當 current 為 null 時，從堆疊中彈出一個節點。這個彈出的節點就是當前應該訪問的節點。將其值加入 result 陣列。

   • 轉向右子樹： 將 current 指針移動到彈出節點的右子節點 (current = poppedNode->right)，準備探索右子樹。

時間複雜度： O(N)，因為每個節點會被推入和彈出堆疊一次。

空間複雜度： O(H)，其中 H 是樹的高度，用於堆疊。最壞情況下為 O(N)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    private $result = []; // 用於儲存遞迴遍歷結果

    /**
     * 遞迴解法
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root) {
        $this->result = []; // 每次呼叫時重置結果陣列
        $this->inorderRecursive($root);
        return $this->result;
    }

    private function inorderRecursive($node) {
        if ($node === null) {
            return;
        }

        // 遍歷左子樹
        $this->inorderRecursive($node->left);
        // 訪問根節點
        $this->result[] = $node->val;
        // 遍歷右子樹
        $this->inorderRecursive($node->right);
    }

    /**
     * 迭代解法 (使用堆疊)
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversalIterative($root) {
        $result = [];
        $stack = []; // 使用陣列模擬堆疊
        $current = $root;

        while ($current !== null || !empty($stack)) {
            // 深入左子樹，將所有左子節點推入堆疊
            while ($current !== null) {
                array_push($stack, $current);
                $current = $current->left;
            }

            // 當前節點為 null，表示到達最左邊的節點
            // 從堆疊中彈出節點（這是現在要訪問的節點）
            $current = array_pop($stack);
            $result[] = $current->val; // 訪問節點

            // 轉向右子樹
            $current = $current->right;
        }

        return $result;
    }
}
?>

---

搭配例題２｜ (102) Binary Tree Level Order Traversal

問題描述

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

給定一個二元樹的根節點 root，返回其層次遍歷的節點值。（即：從左到右，逐層遍歷）。

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]

Output: [[1]]

Example 3:

Input: root = []

Output: []

解題思路

層次遍歷（Level Order Traversal），又稱廣度優先搜尋（BFS），是按照樹的層級從上到下、從左到右依次訪問所有節點。它通常使用佇列（Queue）來實現。

迭代解法 (使用佇列 - Queue)：

1. 初始化：

   • 創建一個空的結果陣列 result，用來儲存每一層的節點值。

   • 如果 root 為 null，直接返回空的 result。

   • 創建一個空的佇列 queue。

   • 將根節點 root 放入佇列。

2. 遍歷：

   • 當佇列不為空時，持續執行迴圈。每次迴圈代表處理當前層的所有節點。

   • 獲取當前層節點數量： 在處理當前層之前，先記錄佇列中節點的數量 levelSize。這個數量就是當前層的節點數。

   • 創建當前層列表： 創建一個空的陣列 currentLevelNodes，用來儲存當前層的所有節點值。

   • 處理當前層節點： 使用一個 for 迴圈，迭代 levelSize 次：

     • 從佇列中取出一個節點 node（使用 array_shift 模擬佇列的dequeue操作）。

     • 將 node->val 加入 currentLevelNodes 陣列。

     • 如果 node 有左子節點 (node->left !== null)，將其加入佇列。

     • 如果 node 有右子節點 (node->right !== null)，將其加入佇列。

   • 將當前層加入結果： 將 currentLevelNodes 陣列添加到 result 陣列中。

3. 返回：

   • 迴圈結束後，返回 result 陣列。

時間複雜度： O(N)，其中 N 是樹的節點數。每個節點都會被放入和取出佇列一次。

空間複雜度： O(W)，其中 W 是樹的最大寬度。在最壞情況下（滿二元樹的最後一層），佇列中可能會儲存約 N/2 個節點，所以空間複雜度是 O(N)。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        $result = []; // 用於儲存最終的層次遍歷結果
        
        if ($root === null) {
            return $result; // 如果根節點為空，返回空陣列
        }

        $queue = []; // 創建一個佇列
        array_push($queue, $root); // 將根節點放入佇列

        // 當佇列不為空時，持續進行層次遍歷
        while (!empty($queue)) {
            $levelSize = count($queue); // 獲取當前層的節點數量
            $currentLevelNodes = []; // 儲存當前層的節點值

            // 遍歷當前層的所有節點
            for ($i = 0; $i < $levelSize; $i++) {
                $node = array_shift($queue); // 從佇列頭部取出節點 (dequeue)
                $currentLevelNodes[] = $node->val; // 將節點值加入當前層列表

                // 如果有左子節點，將其加入佇列
                if ($node->left !== null) {
                    array_push($queue, $node->left);
                }
                // 如果有右子節點，將其加入佇列
                if ($node->right !== null) {
                    array_push($queue, $node->right);
                }
            }
            // 將當前層的節點值列表加入最終結果
            $result[] = $currentLevelNodes;
        }

        return $result;
    }
}
?>

---

二元搜尋樹 (BST, Binary Search Tree) 🔍

二元搜尋樹（Binary Search Tree, BST）是一種特殊的二元樹，它遵循以下原則：

• 每個節點的值都比其左子樹中所有節點的值大。

• 每個節點的值都比其右子樹中所有節點的值小。

• 其左右子樹也都是二元搜尋樹。

  這些特性使得 BST 能夠高效地進行搜尋、插入和刪除操作，平均時間複雜度為 O(logn)。

搭配例題１｜ (700) Search in a Binary Search Tree

問題描述

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

給定一個二元搜尋樹（BST）的根節點 root 和一個整數 val。

在 BST 中找到節點值等於 val 的節點，並返回以該節點為根的子樹。如果不存在這樣的節點，則返回 null。

Example 1:

Input: root = [4,2,7,1,3], val = 2

Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5

Output: []

解題思路

在二元搜尋樹中搜尋一個值，可以利用其有序性來高效地進行。與普通二元樹不同，我們不需要遍歷所有節點，只需根據目標值與當前節點值的比較結果來決定向左還是向右子樹搜尋。

遞迴解法：

1. 基本情況 (Base Cases)：

   • 如果當前節點 root 為 null，表示已經到達樹的末端，但仍未找到目標值，返回 null。

   • 如果當前節點的值 root->val 等於目標值 val，表示找到目標節點，返回 root。

2. 遞迴步驟 (Recursive Step)：

   • 如果 val < root->val，表示目標值可能在左子樹中。遞迴地在 root->left 中搜尋：searchBST(root->left, val)。

   • 如果 val > root->val，表示目標值可能在右子樹中。遞迴地在 root->right 中搜尋：searchBST(root->right, val)。

時間複雜度： 平均情況下為 O(logN)，其中 N 是 BST 的節點數，因為每一步都將搜尋範圍減半。最壞情況下（斜樹）為 O(N)。

空間複雜度： 平均情況下為 O(logN)，用於遞迴呼叫堆疊。最壞情況下為 O(N)。

迭代解法：

迭代解法使用一個 current 指針來遍歷樹，直到找到目標值或 current 變為 null。

1. 初始化：

   • 創建一個 current 指針，初始化為 root。

2. 遍歷：

   • 當 current 不為 null 時，持續執行迴圈。

   • 比較：

     • 如果 current->val == val，表示找到目標值，返回 current。

     • 如果 val < current->val，將 current 移動到其左子節點 (current = current->left)。

     • 如果 val > current->val，將 current 移動到其右子節點 (current = current->right)。

3. 返回：

   • 如果迴圈結束（即 current 變為 null），表示未找到目標值，返回 null。

時間複雜度： 與遞迴解相同，平均 O(logN)，最壞 O(N)。

空間複雜度： O(1)，因為只使用了常數額外的變數。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    /**
     * 遞迴解法
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function searchBST($root, $val) {
        // 基本情況 1: 節點為空，表示未找到目標值
        if ($root === null) {
            return null;
        }
        
        // 基本情況 2: 找到目標值
        if ($root->val === $val) {
            return $root;
        }

        // 如果目標值小於當前節點值，向左子樹搜尋
        if ($val < $root->val) {
            return $this->searchBST($root->left, $val);
        } 
        // 如果目標值大於當前節點值，向右子樹搜尋
        else {
            return $this->searchBST($root->right, $val);
        }
    }

    /**
     * 迭代解法
     * @param TreeNode $root
     * @param Integer $val
     * @return TreeNode
     */
    function searchBSTIterative($root, $val) {
        $current = $root; // 從根節點開始

        while ($current !== null) {
            if ($current->val === $val) {
                return $current; // 找到目標節點，返回
            } elseif ($val < $current->val) {
                $current = $current->left; // 目標值較小，向左移動
            } else {
                $current = $current->right; // 目標值較大，向右移動
            }
        }

        return null; // 遍歷完畢仍未找到，返回 null
    }
}
?>

---

搭配例題２｜ (098) Validate Binary Search Tree

問題描述

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with values less than the node's value.

• The right subtree of a node contains only nodes with values greater than the node's value.

• Both the left and right subtrees must also be binary search trees.

給定一個二元樹的根節點 root，判斷它是否是一個有效的二元搜尋樹 (BST)。

一個有效的 BST 定義如下：

• 一個節點的左子樹只包含值小於該節點值的節點。

• 一個節點的右子樹只包含值大於該節點值的節點。

• 左右子樹也必須是二元搜尋樹。

Example 1:

Input: root = [2,1,3]

Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4, which is less than 5.

解題思路

驗證一個二元樹是否是有效的 BST，不能僅僅檢查每個節點的值是否大於其左子節點且小於其右子節點。因為 BST 的性質是「左子樹中的所有節點都小於根節點，右子樹中的所有節點都大於根節點」，這是一個遞歸的全局性約束。

例如，在 [5,1,4,null,null,3,6] 這個例子中，雖然 4 > 1 且 4 < null，但 4 作為 5 的右子樹的根，它必須大於 5，但實際 4 < 5，所以這不是一個有效的 BST。

因此，我們需要維護一個**範圍（最小值 min 和最大值 max）**來檢查每個節點的值。

遞迴解法（帶範圍檢查）：

1. 輔助函式定義： 創建一個輔助函式 isValidBSTHelper(node, min, max)，它接收當前節點 node，以及 node 值必須遵守的最小值 min 和最大值 max 限制。

2. 基本情況 (Base Case)：

   • 如果 node 為 null，表示到達葉子節點之外，這個路徑是有效的，返回 true。

3. 檢查當前節點：

   • 如果 min 不為 null 且 node->val <= min，則當前節點的值不符合最小值限制，返回 false。

   • 如果 max 不為 null 且 node->val >= max，則當前節點的值不符合最大值限制，返回 false。

4. 遞迴檢查子樹：

   • 檢查左子樹： 遞迴呼叫 isValidBSTHelper(node->left, min, node->val)。左子樹中的所有節點值必須介於 min 和 node->val 之間（即上限更新為當前節點值）。

   • 檢查右子樹： 遞迴呼叫 isValidBSTHelper(node->right, node->val, max)。右子樹中的所有節點值必須介於 node->val 和 max 之間（即下限更新為當前節點值）。

   • 只有當這兩個遞迴呼叫都返回 true 時，才返回 true。

主函式 isValidBST(root) 第一次呼叫輔助函式時，min 和 max 可以分別設定為負無限大和正無限大（或 null，表示沒有下限/上限）。

時間複雜度： O(N)，其中 N 是樹的節點數，因為每個節點都會被訪問一次。

空間複雜度： O(H)，其中 H 是樹的高度，用於遞迴呼叫堆疊。最壞情況下（斜樹），H 可以是 N，所以空間複雜度可能是 O(N)。

中序遍歷解法（進階）：

一個 BST 的中序遍歷會得到一個遞增的序列。我們可以利用這個特性來驗證 BST。

1. 執行樹的中序遍歷，將所有節點的值儲存到一個列表中。

2. 檢查這個列表是否是嚴格遞增的。如果不是，則它不是一個有效的 BST。

   這個方法需要額外的空間來儲存中序遍歷的結果。

優化： 在中序遍歷的同時進行檢查，而無需儲存整個列表。只需維護一個 prevVal 變數，儲存上一個訪問過的節點值。每次訪問當前節點時，比較 current->val 是否嚴格大於 prevVal。

1. 初始化： 設置 prevVal = null 或一個足夠小的數值（如 PHP_INT_MIN），表示初始沒有前一個值。

2. 遍歷： 使用中序遍歷（遞迴或迭代）。

   • 在訪問根節點之前：遞迴檢查左子樹。

   • 在訪問根節點時：

     • 如果 prevVal 不為 null 且 current->val <= prevVal，則不是 BST，返回 false。

     • 更新 prevVal = current->val。

   • 在訪問根節點之後：遞迴檢查右子樹。

這種優化將空間複雜度保持在 O(H)（遞迴堆疊），同時避免了額外儲存整個中序列表。

PHP 程式碼

PHP

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * public $val = null;
 * public $left = null;
 * public $right = null;
 * function __construct($val = 0, $left = null, $right = null) {
 * $this->val = $val;
 * $this->left = $left;
 * $this->right = $right;
 * }
 * }
 */
class Solution {
    /**
     * 遞迴解法 (帶有上下限檢查)
     * @param TreeNode $root
     * @return Boolean
     */
    function isValidBST($root) {
        // 初始呼叫時，min 和 max 設為 null，表示沒有上下限
        return $this->isValidBSTHelper($root, null, null);
    }

    /**
     * 輔助函式：遞迴檢查 BST 的有效性
     * @param TreeNode $node 當前節點
     * @param mixed $min_val 當前子樹中節點允許的最小值 (可以是 null)
     * @param mixed $max_val 當前子樹中節點允許的最大值 (可以是 null)
     * @return Boolean
     */
    private function isValidBSTHelper($node, $min_val, $max_val) {
        // 基本情況: 空節點是有效的 BST
        if ($node === null) {
            return true;
        }

        // 檢查當前節點的值是否在允許的範圍內
        // 如果有最小值限制且當前節點值小於等於最小值，則無效
        if ($min_val !== null && $node->val <= $min_val) {
            return false;
        }
        // 如果有最大值限制且當前節點值大於等於最大值，則無效
        if ($max_val !== null && $node->val >= $max_val) {
            return false;
        }

        // 遞迴檢查左子樹:
        // 左子樹的所有節點值必須小於當前節點的值 ($node->val)
        // 最小值限制不變
        $leftValid = $this->isValidBSTHelper($node->left, $min_val, $node->val);
        if (!$leftValid) {
            return false;
        }

        // 遞迴檢查右子樹:
        // 右子樹的所有節點值必須大於當前節點的值 ($node->val)
        // 最大值限制不變
        $rightValid = $this->isValidBSTHelper($node->right, $node->val, $max_val);
        if (!$rightValid) {
            return false;
        }

        // 如果左右子樹都有效，且當前節點也有效，則返回 true
        return true;
    }

    // 第二種解法：中序遍歷 (Inorder Traversal)
    // 注意：因為 LeetCode 每次執行測試都會創建新的 Solution 實例，
    // 所以 prevVal 和 isFirstNode 需要在每次呼叫 isValidBSTInorder 時重置。
    private $prevVal = null; // 用於儲存中序遍歷中上一個訪問的節點值
    private $isFirstNode = true; // 標記是否為中序遍歷的第一個節點，因為第一個節點沒有前一個值可比

    /**
     * 中序遍歷解法
     * @param TreeNode $root
     * @return Boolean
     */
    function isValidBSTInorder($root) {
        $this->prevVal = null; // 重置 prevVal
        $this->isFirstNode = true; // 重置標記
        return $this->inorderCheck($root);
    }

    private function inorderCheck($node) {
        if ($node === null) {
            return true;
        }

        // 遞迴檢查左子樹
        if (!$this->inorderCheck($node->left)) {
            return false;
        }

        // 檢查當前節點 (中序遍歷的「訪問根節點」步驟)
        // 如果不是第一個節點，且當前節點值小於等於前一個節點值，則不是 BST
        if (!$this->isFirstNode && $node->val <= $this->prevVal) {
            return false;
        }
        $this->prevVal = $node->val; // 更新 prevVal 為當前節點的值
        $this->isFirstNode = false; // 標記為非第一個節點

        // 遞迴檢查右子樹
        return $this->inorderCheck($node->right);
    }
}
?>

---

位元運算 (Bitwise Operation) 💡

位元運算（Bitwise Operation）直接操作整數的二進位位。這些操作通常比傳統的算術運算和邏輯運算更快，因為它們直接在處理器的層級上工作。位元運算在解決某些特定演算法問題（如查找唯一數、交換變數等）時非常高效且優雅。常見的位元運算包括：AND (&)、OR (|)、XOR (^)、NOT (~) 、左移 (<<)、右移 (>>)。

搭配例題１｜ (136) Single Number

問題描述

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

給定一個非空的整數陣列 nums，除了其中一個元素只出現一次外，其餘每個元素都出現兩次。找出那個只出現一次的元素。

你必須實作一個具有線性時間複雜度並只使用常數額外空間的解法。

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

解題思路

這是一個非常經典的位元運算問題，主要利用了 XOR (異或) 運算的以下特性：

1. 任何數與 0 異或，結果仍是該數本身： a ^ 0 = a

2. 任何數與自身異或，結果為 0： a ^ a = 0

3. 異或運算滿足交換律和結合律： a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

根據這些特性，如果我們將陣列中所有數字進行異或操作，那麼所有出現兩次的數字最終會因為 a ^ a = 0 而相互抵消，只剩下那個唯一出現一次的數字。

演算法步驟：

1. 初始化： 創建一個變數 singleNumber 並初始化為 0。

2. 遍歷陣列： 遍歷 nums 陣列中的每個數字 num。

3. 異或操作： 將 singleNumber 與當前的 num 進行異或操作：singleNumber = singleNumber ^ num。

4. 返回結果： 遍歷結束後，singleNumber 中儲存的值就是那個只出現一次的數字。

時間複雜度： O(N)，其中 N 是陣列的長度，因為我們只需要遍歷陣列一次。

空間複雜度： O(1)，因為我們只使用了常數個額外變數。這符合題目要求。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $singleNumber = 0; // 初始化結果為 0

        // 遍歷陣列中的每個數字
        foreach ($nums as $num) {
            // 將結果與當前數字進行異或操作
            // 特性：a ^ a = 0，a ^ 0 = a
            // 所有出現兩次的數字都會相互抵消，只剩下唯一的數字
            $singleNumber ^= $num; 
        }

        return $singleNumber; // 返回只出現一次的數字
    }
}
?>

---

搭配例題２｜ (693) Binary Number with Alternating Bits

問題描述

Given a positive integer n, return true if every two adjacent bits in its binary representation are different, otherwise return false.¹

給定一個正整數 n，如果其二進位表示中每兩個相鄰的位元都不同，則返回 true，否則返回 false。²

Example 1:³

Input: n = 5

Output: true

Explanation: The binary representation of 5 is: 1014

Example 2:⁵

Input: n = 7

Output: false

Ex6planation: The binary representation of 7 is: 111

Example 3:

Input: n = 11

Output: false

Explanation: The binary representation of 11 is: 1011

解題思路

判斷一個正整數的二進位表示是否是交替位元，意味著其二進位形式應該是像 ...10101 或 ...01010 這樣的模式。

方法一：逐位元檢查 (Iterative Bitwise Check)

我們可以透過不斷地右移數字並比較相鄰位元來檢查。

1. 迴圈遍歷： 只要 n 不為 0，就持續執行迴圈。

2. 提取最低位和次低位：

   • 最低位（最右邊的位元）可以透過 n & 1 獲得。

   • 次低位（倒數第二個位元）可以透過 (n >> 1) & 1 獲得。

3. 比較： 在每次右移之前，我們需要比較當前最低位 (n & 1) 與其左邊一位（也就是右移一位後的最低位）。

   • 儲存當前最低位：lastBit = n & 1。

   • 將 n 右移一位：n >>= 1。

   • 比較現在新的最低位 (n & 1) 是否與 lastBit 相同。如果相同，則不符合交替位元的條件，返回 false。

4. 返回結果： 如果迴圈正常結束（即所有相鄰位元都不同），返回 true。

時間複雜度： O(logn)，因為我們遍歷了數字的位元數，大約是 log2(n) 次。

空間複雜度： O(1)。

方法二：巧妙的位元運算 (Clever Bitwise Operation)

這個方法利用了位元運算的一個特性來簡化判斷。

如果一個數 n 的位元是交替的（例如 10101），那麼將 n 右移一位後 (n >> 1)，得到的值（例如 01010），與原來的 n 進行 XOR 操作，會得到一個所有位元都為 1 的數（例如 11111）。

例如：

n = 5 (二進位是 0101)

n >> 1 = 2 (二進位是 0010)

n ^ (n >> 1) = 0101 ^ 0010 = 0111 (十進位是 7)

接下來，我們需要判斷這個所有位元都為 1 的數（例如 0111）是否真的是一個「全 1」的數。一個「全 1」的數的特性是，將它加 1 後，結果將是 1 後面跟著一串 0（即 2 的冪）。然後，將這個 2 的冪與原來的「全 1」的數進行 AND 操作，結果會是 0。

例如：

num_all_ones = 7 (二進位是 0111)

num_all_ones + 1 = 8 (二進位是 1000)

num_all_ones & (num_all_ones + 1) = 0111 & 1000 = 0000 (十進位是 0)

所以，演算法步驟是：

1. 計算 n 與 n 右移一位的異或結果：xor_result = $n ^ ($n >> 1)。

2. 檢查 xor_result 是否為一個全 1 的數：return ($xorResult & ($xorResult + 1)) === 0;

時間複雜度： O(1)，因為只執行了常數次位元運算。

空間複雜度： O(1)。

PHP 程式碼

PHP

<?php

class Solution {
    /**
     * 方法一：逐位元檢查
     * @param Integer $n
     * @return Boolean
     */
    function hasAlternatingBits($n) {
        // 從第二個位元開始檢查 (與最低位比較)
        // 迴圈條件 $n > 0 確保遍歷完所有位元
        while ($n > 0) {
            // 獲取當前最低位 (current_bit)
            $current_bit = $n & 1;
            
            // 將 n 右移一位，以便在下一次迭代中獲取新的最低位（即原本的次低位）
            $n >>= 1;

            // 檢查新的最低位（原本的次低位）是否與之前儲存的最低位相同
            // 如果 n 已經為 0 (只剩下一位)，則不需要再比較
            if (($n > 0) && (($n & 1) === $current_bit)) {
                return false; // 有相鄰位元相同，不符合交替位元條件
            }
        }
        return true; // 所有位元都檢查完畢且無相鄰相同，返回 true
    }

    /**
     * 方法二：巧妙的位元運算
     * @param Integer $n
     * @return Boolean
     */
    function hasAlternatingBitsClever($n) {
        // Step 1: 將 n 與 n 右移一位的結果進行異或操作
        // 如果 n 的位元是交替的，這個結果會是一個全 1 的數
        // 例如：n = 5 (0101), n >> 1 = 2 (0010)
        //       xorResult = 0101 ^ 0010 = 0111 (7)
        $xorResult = $n ^ ($n >> 1);

        // Step 2: 判斷 xorResult 是否為一個全 1 的數
        // 一個全 1 的數 x (例如 0111)，其特性是 x & (x + 1) == 0
        // 因為 x + 1 會是 1 後面跟著一串 0 (例如 0111 + 1 = 1000)
        // 兩者進行 AND 運算，結果會是 0
        return ($xorResult & ($xorResult + 1)) === 0;
    }
}
?>