iT邦幫忙

2025 iThome 鐵人賽

DAY 12
0
自我挑戰組

Leetcode 自學系列 第 12

自學Leetcode Day12

  • 分享至 

  • xImage
  •  

145. Binary Tree Postorder Traversal
1.後序遍歷:
遍歷順序為:
左子樹 (Left)
右子樹 (Right)
根節點 (Root)
2.解題思路:兩個 Stack(直觀寫法)
核心想法:

  • 第一個 stack 用來模擬後序遍歷。
  • 第二個 stack(或用 list 反轉)儲存訪問順序,最後反轉即為正確的 Postorder。
    步驟:
    1.建立兩個 stack:
    • stack1:用來處理節點。
    • stack2:儲存節點訪問順序(根 ➝ 右 ➝ 左),最後反轉。
      2.將 root 推入 stack1。
      3.當 stack1 不為空時:
    • 彈出一個節點 node,加入 stack2。
    • 將 node.left 推入 stack1
    • 將 node.right 推入 stack1
      4.將 stack2 反轉後即為正確結果。
      3.簡單範例解析
      範例
      對於樹:https://ithelp.ithome.com.tw/upload/images/20250926/20169241XjeVRqhNQW.jpg

執行流程(stack2 的最終內容):4, 5, 2, 3, 1
4.程式碼截圖:https://ithelp.ithome.com.tw/upload/images/20250925/20169241LD5RU4RwTE.png
5.此次選的題目跟前一天差不多只是差在今天的是後序解法,當然我有自己想過解題思路以及用遞迴如何解答,我也有順利解出來只是我在參考前一天的非遞迴用法,便應用在今天的題目上時還是有遇到一些小問題,但是在程式碼的部分我有比前一次又更清楚了解這類型的題目了。


上一篇
自學Leetcode Day11
下一篇
自學Leetcode Day13
系列文
Leetcode 自學16
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言