從零開始學Python (23)\u200a—\u200a資料結構模組deque：旁人來來去去像行雲流水

Day 23 資料結構模組deque：旁人來來去去像行雲流水

註：本篇文章同步刊載於iT邦幫忙，為鐵人賽之系列文章。
https://ithelp.ithome.com.tw/articles/10247295

先來解一下上次的練習吧！

我們唯一需要動的應該只有calculate的函式，
當 p1 < p2 時，將兩個值交換即可。
別忘了交換應該要連同Entry裡面的值都一起換(price1/price2)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
### calculate函式用來接受按鈕事件，取得商品價格及折扣方式，計算後輸出
def calculate():
    # 每次要計算時，都讓按鈕顯示計算哪一個折扣法
    btnstr.set('計算' + radiostr.get() + '中')
    # 用try...except...的方式來避免掉輸入的不是數字
    try:
        choice = radiostr.get() # radiobutton的選擇項
        p1 = int(price1.get())
        p2 = int(price2.get())
        if p1 <= 0 or p2 <= 0: # 如果輸入<=0的數字也當成例外處理
            raise Exception()
        if p1 < p2:
            p1, p2 = p2, p1
            price1.set(str(p1))
            price2.set(str(p2))
...(下面沒有變動XD)

我們今天要來談談deque的應用，
我們前面已經在第十一篇的部分提到過deque的用法，這篇主要要來補充deque作為queue時的常見狀況。

一般我們提到兩種資料結構：
queue(佇列)或stack(堆疊)的概念，
其實就是先進先出(FIFO, First-In-First-Out)或
先進後出(First-In-Last-Out)的區別。

queue就好像排隊一樣，當然是先排的先被服務到(除非有人插隊XD)；
stack則像是一疊文件一樣，假設你都拿最上面的，
當老闆又往上放新的文件(工作)給你的時候，
你再拿就會拿到最新放上去的囉！
這兩者在不同的程式語言有時候會有不同的稱呼和變形，
但本質是不變的。

那麼，什麼狀況下我們寫程式會容易用到queue(deque)呢?
最常見的狀況是遇到一個Tree(樹)的問題的時候！
那，什麼是樹呢？
好問題！這個問題應該要用比較長的篇幅解釋，
所以請讀者參閱拙作從LeetCode學演算法的第十四篇，
下面我們再繼續。

不囉嗦，我們直接上一道題目作為範例吧！
上面的連結應該已經介紹過二元樹了，
最簡單來說，一棵二元樹就是由根節點(root)，
及左子樹(left tree)/右子樹(right tree)所構成。
每個節點上有可能連結左右節點，
也可能沒有連接，稱為NIL，在Python為None。
如果我們今天想要按照一層一層順序來走遍整個樹，
並分層記錄的話，該怎麼做呢？
這個問題通常被稱為Level-order Traversal。(層序遍歷)
讀者可以前往LeetCode的題目看更詳細的描述。
https://leetcode.com/problems/binary-tree-level-order-traversal/
我們可以先走第一層，再走第二層，以此類推，
那麼這中間走完第一層時，怎麼知道第二層有哪些節點呢？
按順序的話，我們應該將第一層的每個節點的左節點/右節點，
放入到一個可以按照放入的順序處理的資料結構，
接著再從這個資料結構裡一個一個拿出來(這時候是第二層了!)，
找每一個的左右節點，再放進去……
咦？這個資料結構不就是queue嗎XD？

我們在解題和寫程式的時候，
可以先把要怎麼做大略寫出來，
再根據這個概念和做法，寫出具體的程式。

以這個問題來說，
題目應該會給出這個二元樹的根節點root，
接著要做的事情就如上面說的一樣，但我們需要一些細部的東西：

開一個res(result)作為存放答案用的串列。
我們先檢查root是否存在，有些題目壞壞的會給None，
如果不存在就直接回傳空的答案給它!
將root放入我們檢查的資料結構(因為它是第一層)，我們先叫它q吧!
開始一個迴圈，當q裡面還有節點時，代表還要繼續。
我們先記下q裡面的個數(命名為cnt)，後面放進去q的都是下一層的節點。
接著先設定一個level變數，用以記錄這層的節點值們。
在裡面再開一個迴圈，這次直接指定跑cnt次，
這樣所有這層的節點都會被我們取出來。
內層迴圈中，每次從q取出一個節點(popleft)，
將節點值(.value)append到level中，
檢查左節點，如果不是None的話就將節點放到q裡。
檢查右節點，做相同的事情XD
內層迴圈結束後，這時候我們拿到一整層的節點值，
我們應該要將其append到res這個結果裡。
最後全部處理完後，可以將res回傳。

好啦!經過上面的步驟，有沒有發現我們其實已經把程式寫完了呢？
只要按著順序對照，應該可以順利寫出答案。

那麼，我們就來看看實際的做法：

1
2
3
4
5
6
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

1
from collections import deque

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = [] # result，用以記錄結果
        if not root: return res # 我們有提過，if not可以用來檢查東西是不是空的
        q = deque([root]) # deque的初始化，要以list的形式放入
        while q: # 當q還有節點(同樣這相當於檢查是不是空的)
            cnt = len(q) # deque支援len的操作(取長度)
            level = [] # 記錄每層的節點值
            for _ in range(cnt): # _沒有特別意思，通常是當沒有要在迴圈內用到時可以使用
                n = q.popleft() # popleft等於從deque的左邊取出，也就是queue的用法
                level.append(n.val) # 取值
                if n.left: q.append(n.left) # 將左節點放入q
                if n.right: q.append(n.right) # 將右節點放入q
            res.append(level) # 每層完成後，要將一整層的節點值list放到res中

        return res # 回傳，結束！

應該不算太難(吧)…?
請務必要看完樹的那篇定義再來看這篇喲！
總言之，deque作為queue使用時，主要會用popleft()跟append()來操作，
同時它會適合按先後順序放入及取出的情況。

練習題目的話，
讀者可以再嘗試看看LeetCode的另一題：
101. Symmetric Tree

那麼，我們就明天見囉！

工商時間：

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode