原住民族考試四等考試-電子工程類科計算機概要106 年第 16 題單選題
對一個有 12 個節點的二元搜尋樹（Binary Search Tree）作後序訪問（Postorder Traversal），並依序輸出訪問節點的數值，其結果如下（次序由左至右）：3, 4, 6, 5, 8, 15, 19, 18, 16, 12, 24, 20。在此樹中有多少個節點為葉節點（Leaf）？
C正確答案
後序遍歷最後是根20，BST左小右大切分後重建樹，葉節點共5個：3,8,15,19,24。
為什麼答案是 C
重建後：根20，左子樹根12(含3,4,6,5,8,15,19,18,16)，右子樹根24。葉節點為3、8、15、19、24，共5個。
載入中…
完整詳解
Pro · 無限重點 後序遍歷最後是根20，BST左小右大切分後重建樹，葉節點共5個：3,8,15,19,24。
後序最後一個是根(20)，前面分成<20的左子樹與>20的右子樹，遞迴切分即可還原樹。
逐選項分析
B✕ 陷阱
可能漏算某個葉節點(如19或24)，常見是忘了單獨的右子樹葉。
C✓ 正確
重建後：根20，左子樹根12(含3,4,6,5,8,15,19,18,16)，右子樹根24。葉節點為3、8、15、19、24，共5個。
D✕ 陷阱
若把內部節點(如6或18)誤認為葉節點會多算，重建樹時須仔細檢查子節點。
樹重建結果 (根=20)
| 節點 | 左子 | 右子 | 是否為葉 |
|---|
| 20 | 12 | 24 | 否 |
| 12 | 5 | 16 | 否 |
| 5 | 4 | 8 | 否 |
| 4 | 3 | - | 否 |
| 3 | - | - | ✅葉 |
| 8 | - | - | ✅葉 |
| 16 | 15 | 18 | 否 |
| 15 | - | - | ✅葉 |
| 18 | - | 19 | 否 |
| 19 | - | - | ✅葉 |
| 24 | - | - | ✅葉 |
後序遍歷的根在最後(不是最前)，很多人誤把3當根就全錯。BST特性是左子樹<根<右子樹，配合後序最後為根，才能遞迴切出左右子樹並重建整棵樹。 
