再探鏈結串列與樹結構

在前三天的刷題實戰中，我們一起實作了線性的鏈結串列和非線性的樹相關的題目。其實你仔細回顧一下，你會發現其實這三題的解法都有一些共同的觀點，像是都會利用「迴圈迭代」的暴力法和「遞迴法」來實現：

• LeetCode 雙刀流：206. Reverse Linked List
  • 方法 ①：交換法
  • 方法 ②：遞迴（recursion）
• LeetCode 雙刀流：700. Search in a Binary Search Tree
  • 方法 ①：迴圈迭代法
  • 方法 ②：遞迴（recursion）
• LeetCode 雙刀流：144. Binary Tree Preorder Traversal
  • 方法 ①：Brute force
  • 方法 ②：遞迴（recursion）

今天我們想要從「遞迴法」的概念延伸，介紹一種稱為「堆疊（Stack）」的抽象資料結構。遞迴法其實是鏈結串列（Linked List）或樹（Tree）當中典型的方法，其概念是「對資料結構中每一個節點做類似的操作，持續執行直到每一個點都跑過一輪」。但這兩種資料結構的差別在於鏈結串列是單一且唯一方向的，但是樹的結構有兩種以上的分支，因此可能會有不同的遍歷找法。

從遞迴策略遷移到堆疊暫存

遞迴策略是一個 Function 中含有自我呼叫的行為，這個過程會將執行到一半的結果先暫存起來，先執行下一個 Function 直到終止條件之後再一個一個 return 回上層。遞迴中的「將執行到一半的結果先暫存起來」是由作業系統處理，當遞迴太深的時候可能就會造成記憶體的問題。

但是在資料結構中有一種抽象資料結構（ADT，Abstract Data Type）稱為「堆疊」，堆疊是指符合先進後出（First In, Last Out）特性的有序線性容器（如下圖）。但抽象資料結構的定義就是你不用管內部怎麼實作，所以一般來說可以利用陣列或是列表來實現都可以。

利用堆疊（Stack）刻意優化

利用 Stack 優化 206. Reverse Linked List

因為堆疊有「先進後出」特性，所以恰恰就符合倒序的概念（Reverse），只要利用 Stack 依序取出 Linked List 中的每個元素，取出的順序就會是倒序的結果。

那我們先用 Python 實作看看

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return None
        stack = []
        while head:
            stack.append(head)
            head = head.next
        
        current = stack.pop()
        head = current
        while stack:
            current.next = stack.pop()
            current = current.next
        current.next = None
        return head

也可以用 JavaScript 復刻一次

var reverseList = function(head) {
    if(head === null) return head;
    let stack = [];
    while(head !== null){
        stack.push(head);
        head = head.next;
    }
    let current = stack.pop();
    head = current;
    while(stack.length > 0){
        current.next = stack.pop();
        current = current.next;
    }
    current.next = null;
    return head;
};

利用 Stack 優化 700. Search in a Binary Search Tree

本題考的是二元搜尋樹當中的元素是否符合目標值，直覺的方法就是利用二元搜尋樹「左小右大」的特性一個一直找。這個是這裡的一個一直找會受限於樹的非線性而有不同的找法，這種方法會先將樹中的資料存到 Stack 中，取出的過程進行檢查。補充一下，用 Stack 去遍歷樹中每一個點的找法稱為「深度優先搜尋（DFS，Depth-First Search）」，後續的文章會提到。

那我們先用 Python 實作看看

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root: return root
        stack = [root];
        while stack:
            node = stack.pop();
            if node.val == val:
                return node
            if node.val > val and node.left:
                stack.append(node.left);
            if node.val < val and node.right:
                stack.append(node.right);
        return None;

也可以用 JavaScript 復刻一次

var searchBST = function(root, val) {
  if (!root) return root;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    if (node.val === val) return node;
    if (node.val > val) {
      if (node.left) stack.push(node.left);
    } else {
      if (node.right) stack.push(node.right);
    }
  }
  return null;
};

利用 Stack 優化 144. Binary Tree Preorder Traversal

延續前一題的想法，遍歷是指要走過樹中每一點的方式，但是因為樹中每一個節點可能會有左/右分支，因此會有「要先找左邊還是右邊」、「要找到最底還是先把周圍的找完」等等的衍生議題。常見的遍歷方法可以分為「前序」、「中序」跟「後序」，依據 Root 被找到的先後做排序，當中的「前序遍歷（Preorder Traversal）」其實就是利用深度優先搜尋去遍歷樹的結果。

那我們先用 Python 實作看看

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res, stack = [], [root]
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.right: stack.append(cur.right)
            if cur.left: stack.append(cur.left)

        return res
    

也可以用 JavaScript 復刻一次

var preorderTraversal = function(root) {
    if(!root) return [];
    let res = [], stack = [root];
    while( stack.length > 0 ){
        let cur = stack.pop();
        res.push(cur.val);
        if(cur.right) stack.push(cur.right);
        if(cur.left) stack.push(cur.left);
    }
    return res;
};

反思沉澱

如同我們在前面講到「刻意優化」的重要性，當寫完一個題目之後可以三個小時、三天，甚是是三週之後再回來看同一個題目，把它當成新的題目重新解解看，反而更容易寫出不一樣的解法。所以這幾天我們就帶大家一起體驗這個過程，從認識新的資料結構開始，嘗試直覺解到遞迴優化，經過三天之後再導入堆疊的實現，這就是一個完整的刷題「優化」體驗。

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。