[LeetCode] #100. Same Tree

-

題目

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

直覺解

構想一：

參考 94. Binary Tree Inorder Traversal，用 Inorder 的方式，遍歷整棵樹，並檢查每個節點的值是否相同

python 3 實作：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: 

    stack_p = [] 

    stack_q = [] 

    while stack_p or stack_q or p or q: 

        if len(stack_p) != len(stack_q): 

            return False 

        if (not p and q) or (p and not q): 

            return False 

             

        if p or q: 

            stack_p.append(p) 

            stack_q.append(q) 

            p = p.left 

            q = q.left 

        else: 

            p = stack_p.pop(len(stack_p) - 1) 

            q = stack_q.pop(len(stack_q) - 1) 

            if p.val != q.val: 

                return False 

            p = p.right 

            q = q.right 

    return True

效能：

Runtime: 32 ms, faster than 59.16% of Python3 online submissions for Same Tree.
Memory Usage: 14.4 MB, less than 28.71% of Python3 online submissions for Same Tree.

構想二：

依照 中間-左邊-右邊 的順序用遞回的方式比對

python 3 實作：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: 

    if (not p and q) or (p and not q): 

        return False 

    if p and q: 

        if p.val != q.val: 

            return False 

        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) 

    return True

犯過的錯誤

  • 因為是 class instance，所以要用 self.isSameTree 呼叫函式，沒加 self. 的話會變成 is not defined

效能：

Runtime: 28 ms, faster than 83.88% of Python3 online submissions for Same Tree.
Memory Usage: 14.3 MB, less than 28.92% of Python3 online submissions for Same Tree.

參考別人的遞迴解後，python 3 易讀性優化：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: 

    if not p and not q: 

        return True 

         

    if not p or not q: 

        return False 

         

    if p.val != q.val: 

        return False 

         

    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

效能：

第一次

Runtime: 48 ms, faster than 8.39% of Python3 online submissions for Same Tree.
Memory Usage: 14.3 MB, less than 28.92% of Python3 online submissions for Same Tree.

第二次

Runtime: 52 ms, faster than 5.81% of Python3 online submissions for Same Tree.
Memory Usage: 14.4 MB, less than 28.92% of Python3 online submissions for Same Tree.

第三次

Runtime: 60 ms, faster than 5.81% of Python3 online submissions for Same Tree.
Memory Usage: 14 MB, less than 95.68% of Python3 online submissions for Same Tree.

第四次

Runtime: 28 ms, faster than 83.88% of Python3 online submissions for Same Tree.
Memory Usage: 14.2 MB, less than 84.85% of Python3 online submissions for Same Tree.

Comments

Post a Comment

Popular posts from this blog

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more