iT邦幫忙

2021 iThome 鐵人賽

DAY 12
1
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 12

LeetCode 雙刀流:144. Binary Tree Preorder Traversal

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)特性的一種延伸操作,不同於線性的搜尋,因為每一個節點可能會有左/右分支,因此有不同的先後順序找法。而不同的找法有時候可以搭配資料結構的特性來使用,以本題來說,我們可以轉換成對每一個點都做一樣的操作,就可以利用遞迴的方式實現。

舉一反三看看相似題

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


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


上一篇
LeetCode 雙刀流:700. Search in a Binary Search Tree
下一篇
線性與非線性的資料結構
系列文
LeetCode 雙刀流:Python x JavaScript30

1 則留言

0
TD
iT邦新手 5 級 ‧ 2021-09-28 09:46:06

以次類推

以「此」類推

WeiYuan iT邦新手 4 級 ‧ 2021-09-28 11:02:22 檢舉

感謝 TD,已修改!

我要留言

立即登入留言