从「递回」策略迁移到「堆叠」暂存

再探链结串列与树结构

在前三天的刷题实战中，我们一起实作了线性的链结串列和非线性的树相关的题目。其实你仔细回顾一下，你会发现其实这三题的解法都有一些共同的观点，像是都会利用「回圈迭代」的暴力法和「递回法」来实现：

• 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 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。