144. Binary Tree Preorder Traversal

今天挑選的是一題「二元樹（Binary Tree）」，二元樹相對於二元搜尋樹來說條件相對沒有那麼嚴謹。這題想考的是「前序遍歷（Preorder Traversal）」，遍歷是指要走過樹中每一點的方式，但是因為樹中每一個節點可能會有左/右分支，因此會有「要先找左邊還是右邊」、「要找到最底還是先把周圍的找完」等等的衍生議題。常見的遍歷方法可以分為「前序」、「中序」跟「後序」，依據 Root 被找到的先後做排序。

先看一下題目描述

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

再搭配範例理解題目

• Example 1:

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

這個題目單純就是實作「前序遍歷（Preorder Traversal）」，算是對於二元樹的基本操作。所謂的前序遍歷就是先找出「中間節點」、再找「左邊節點」、最後才找「右邊節點」以此類推。

開始實作

方法 ①：Brute force

第一個方法可以用兩個迴圈硬幹，用兩層迴圈探訪全部的節點。裡面的迴圈去找每一個點當中的「中間節點」和「左邊節點」，接著再從外層的迴圈去找到「右邊節點」。

用 Python 實作一次

class Solution:
    def preorderTraversalRecursive(self, root: TreeNode) -> List[int]:
        stack, result = [], []
        
        while stack or root:
            while root:
                result.append(root.val)
                stack.append(root)
                root = root.left
            root = stack.pop()
            root = root.right
        
        return result

也可以用 JavaScript 復刻一次

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

方法 ②：遞迴（recursion）

第二種方法搭配 Recursive 的概念，取得「中間節點」之後，再往下的「左邊節點」找、找完再找「右邊節點」，利用遞迴對每一個點都做一樣的規則。

用 Python 實作一次

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = [root.val]
        res.extend(self.preorderTraversal(root.left));
        res.extend(self.preorderTraversal(root.right));
        return res

也可以用 JavaScript 復刻一次

const preorderTraversal = (root) => {
    if (!root) return [];
    let res = [root.val];
    res.push(...preorderTraversal(root.left));
    res.push(...preorderTraversal(root.right));
    return res
};

反思沉澱

遍歷是樹（Tree）特性的一種延伸操作，不同於線性的搜尋，因為每一個節點可能會有左/右分支，因此有不同的先後順序找法。而不同的找法有時候可以搭配資料結構的特性來使用，以本題來說，我們可以轉換成對每一個點都做一樣的操作，就可以利用遞迴的方式實現。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 94. Binary Tree Inorder Traversal
• 589. N-ary Tree Preorder Traversal

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