派生二進制樹從後序列表或預訂列表

Question

我有一個關於二叉樹的問題。所以我知道用於構造二叉樹的前序後序和序列。現在，我如何從樹的後序列表或樹的預訂列表中導出樹的inorder列表。

Answer 1

由於後單列表不提供有關樹形狀的足夠信息，因此無法從後單列表中推導出任何列表。您需要兩個列表（例如後序和前序）才能唯一地重構樹。

一個簡單的反例：

後序上市：A B C

這可能是兩棵樹

C 
    |  C 
    B /\ 
    | A B 
    A 

但序的房源針對這兩個樹種之一是A B C和C B.