已知某二元樹（Binary Tree）的拜訪序列如下：前序（Pre-order）：[8, 10, 9, 1, 3, 7, 12, 6] 中序（In-order）：[10, 9, 1, 8, 12, 7, 3, 6] 試問該二元樹正確的後序（Post-order）拜訪序列為何？

A[10, 9, 1, 12, 7, 6, 3, 8]

B[6, 3, 7, 12, 1, 9, 10, 8]

C[1, 9, 10, 6, 3, 7, 12, 8]

D[1, 9, 10, 12, 7, 6, 3, 8]正確答案

答案與詳解

正確答案

前序首元素為根，切中序左右子樹，遞迴重建後輸出後序：[1,9,10,12,7,6,3,8]。

A[10, 9, 1, 12, 7, 6, 3, 8]左子樹後序✕ 錯誤

左子樹後序順序錯誤。左子樹中序為 [10,9,1]、前序為 [10,9,1]，代表向右鏈下延，後序應為 [1,9,10]，非 [10,9,1]。

B[6, 3, 7, 12, 1, 9, 10, 8]反轉中序陷阱✕ 易錯陷阱

此選項並非正確後序。它是把右子樹中序 [12,7,3,6] 反向成 [6,3,7,12]、左子樹中序 [10,9,1] 反向成 [1,9,10]，再把根 8 放最後；後序必須依樹結構左→右→根重建，不能僅反轉中序序列。

C[1, 9, 10, 6, 3, 7, 12, 8]✕ 易錯陷阱

D[1, 9, 10, 12, 7, 6, 3, 8]✓ 正確

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解

已知某二元樹（Binary Tree）的拜訪序列如下： 前序（Pre-order）：[8, 10, 9, 1, 3, 7, 12, 6] 中序（In-order）：[10, 9, 1, 8, 12, 7, 3, 6] 試問該二元樹正確的後序（Post-order）拜訪序列為何？