#46348: 解題概念


harlivy_forever (噴火水雞肉飯)

學校 : 國立嘉義高級中學
編號 : 160563
來源 : [163.27.3.96]
最後登入時間 :
2025-08-20 10:44:16

我不是很會精簡描述,有點冗長請見諒

前序:根、左、右

中序:左 、根、右

後序:左、右、根

其中雖然根是一樣的單個節點,但左以及右裡字母的順序不一定相同

 

簡單來說,我們的目標是找出輸入字串中分別代表根、左以及右的子字串,調整順序後重新拼在一起,再把這個新字串回傳。左以及右都是個別的子樹,所以也可以分別對它們進行一樣的操作。

 

以下為暴雷,謹慎服用。以第一個範例為例,不像左右可以是子樹,根一定是一個節點,所以我們可以從前序表示法 DBACEGF 得知根是第一個節點 D。中序表示法的根在左和右之間,所以根的左邊就是左,根的右邊就是右。(小提示:前序和中序表示法中,分別代表左跟右的子字串節點順序可能不同,但長度會是一樣的,所以我們可以從長度判斷如何切分每個部分)於是我們得到根 = D,前序的左 = BAC,前序的右 = EGF,中序的左 = ABC,中序的右 = EFG,調換順序再重新拼在一起後,答案會是「後序的左  後序的右  D (後序的根 = 中序的根 = 前序的根)」,注意後序的左以及右和前序還有中序的左以及右不一定相同,所以要做的事就是一樣用拆開再重拼的方式得出後序的左跟後序的右,就一直循環下去。