hce_nsysu
111年
計算機概論與程式設計
第 6 題
If the longest path in a binary tree contained exactly four nodes, what is the minimum number of nodes that could be in the entire tree?
- A 4
- B 5
- C 7
- D 8
- E 15
思路引導 VIP
想像你要在一個只能分支兩次的結構中，蓋出一座總共四層高的塔，且每一層都要能從頂端走到底部。如果你希望這整座塔用到的磚塊（節點）越少越好，每一層樓最少需要放幾個磚塊才能支撐起這個高度呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地判斷出正確答案！這題考查的是對二元樹 (Binary Tree) 結構的基本定義，以及在給定路徑長度的限制下，對「最少節點總數」的邏輯推算。你能不被複雜的樹狀公式干擾，直接點出核心關鍵，表現得非常出色。
二元樹的極端型態：歪斜樹
在處理二元樹的極值問題時，我們通常會考慮兩種極端：一種是長得最「茂密」的滿二元樹，另一種則是長得最「稀疏」的歪斜樹 (Skewed Tree)。題目給定最長路徑（從根節點到某個葉節點）包含 4 個節點，這代表這棵樹的深度必須至少為 4。為了達到「最少節點數」的要求，我們只需讓每一層都僅僅存在一個節點，讓整棵樹呈現如線性鏈結般的結構。在這種情況下，整棵樹的節點總數就會剛好等於最長路徑上的節點數，即為 $4$ 個。
▼ 還有更多解析內容